Güçlü bağlantılılık#2403

Güçlü bağlantılılık (Editoryal)

Problem, yönlü bir grafın güçlü bağlantılı bileşenlerinin sayısının bulunmasını gerektirir. Bunun için iki derinlik öncelikli arama gerçekleştiren Kosaraju algoritmasını kullanırız:

giriş grafı üzerinde bir derinlik öncelikli arama gerçekleştirin ve köşelerin işlenmesinin tamamlandığı sırayı (köşeden çıkış anında) kaydedin;
her kenarın yönünü tersine çevirerek ters grafı oluşturun;
köşeleri, işlenmelerinin tamamlanma sırasının tersi sırayla dolaşın ve henüz ziyaret edilmemiş her köşeden ters graf üzerinde bir derinlik öncelikli arama başlatın. Böyle her başlatma tam olarak bir güçlü bağlantılı bileşeni dolaşır.

Ters graf, orijinal grafla aynı güçlü bağlantılı bileşenlere sahiptir: eğer $u$ 'dan $v$ 'ye ve $v$ 'den $u$ 'ya yollar varsa, kenarlar tersine çevrildikten sonra bu yollar korunur, yalnızca yönleri değişir. İkinci dolaşımda köşelerin işlenme sırası, derinlik öncelikli aramanın mevcut bileşenden dışarı çıkmamasını garanti eder: ulaşabileceği tüm bileşenler bu ana kadar zaten ziyaret edilmiştir.

Cevap, ikinci dolaşımdaki derinlik öncelikli arama başlatma sayısıdır.

Örnek

Örneklerde verilen graflar aşağıda gösterilmiştir. Güçlü bağlantılı bileşenler renkli olarak vurgulanmıştır.

İlk graf hiçbir döngü içermez: herhangi bir köşeye geri dönmek mümkün değildir. Bu nedenle, her köşe ayrı bir güçlü bağlantılı bileşen oluşturur: ${1}$ , ${2}$ , ${3}$ .

İkinci grafta, $1$ , $2$ ve $3$ köşeleri $1 \to 2 \to 3 \to 1$ 1 \to 2 \to 3 \to 1 döngüsü üzerinde bulunur ve tek bir bileşen ${1, 2, 3}$ \{1, 2, 3\} oluşturur. $4$ köşesine $5$ köşesinden ulaşılamaz, bu yüzden $4$ ve $5$ köşeleri ayrı bileşenler olan ${4}$ ve ${5}$ 'i oluşturur. Böylece, her iki grafın da $3$ güçlü bağlantılı bileşeni vardır.

Algoritmayı ikinci graf üzerinde simüle edelim. $1$ köşesinden başlayan ilk derinlik öncelikli arama $1 \to 2 \to 3$ 1 \to 2 \to 3 yolunu izler ve ardından $4$ köşesinden $4 \to 5$ 4 \to 5 yolunu izler. Köşelerin işlenmesinin tamamlandığı sıra $t o p = (3, 2, 1, 5, 4)$ top = (3, 2, 1, 5, 4)'tür. Ters çevirdikten sonra $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3) elde ederiz.

Ters graf, $2 \to 1$ 2 \to 1, $3 \to 2$ 3 \to 2, $1 \to 3$ 1 \to 3 ve $5 \to 4$ 5 \to 4 kenarlarını içerir. İkinci dolaşımı $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3) sırasıyla gerçekleştirin:

$df s 2 (4)$ : $4$ köşesinin ters grafta giden kenarı yoktur, bileşen ${4}$ ;
$df s 2 (5)$ : $5 \to 4$ 5 \to 4 kenarı zaten ziyaret edilmiş bir köşeye gider, bileşen ${5}$ ;
$df s 2 (1)$ : $1 \to 3 \to 2$ 1 \to 3 \to 2 yolunu dolaşın, bileşen ${1, 3, 2}$ \{1, 3, 2\}.

$2$ ve $3$ köşeleri zaten ziyaret edildiğinden, yeni başlatma yoktur. $c = 3$ c = 3 bileşen elde ederiz.

Ters grafta, başka bir bileşene ait olan $4$ köşesine $5$ köşesinden ulaşılabileceğine dikkat edin. Ancak $4$ köşesi $5$ köşesinden önce işlendiğinden, $df s 2 (5)$ çağrıldığında zaten ziyaret edilmiştir ve $5$ köşesinin bileşenine dahil olmaz.

Algoritmanın uygulanması

Giriş grafını $g$ komşuluk listesi olarak, ters grafı ise $g r$ komşuluk listesi olarak saklayın. $u se d$ dizisi ziyaret edilen köşeleri işaretler. $t o p$ dizisi, ilk derinlik öncelikli arama sırasında köşelerin işlenmesinin tamamlandığı sırayı saklar.

vector<vector<int> > g, gr;
vector<int> used, top;

dfs1 fonksiyonu, giriş grafı üzerinde bir derinlik öncelikli arama gerçekleştirir. $v$ köşesi, kendisinden ulaşılabilen tüm köşeler işlendikten sonra, yani kendisinden çıkış anında, $t o p$ dizisinin sonuna eklenir.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

C++

dfs2 fonksiyonu, ters graf üzerinde bir derinlik öncelikli arama gerçekleştirir. Ana programdan yapılan bir $df s 2$ çağrısı sırasında ziyaret edilen tüm köşeler, tek bir güçlü bağlantılı bileşeni oluşturur.

void dfs2(int v)
{
  used[v] = 1;
  for (int to : gr[v])
    if (!used[to]) dfs2(to);
}

Programın ana bölümü. Giriş grafını okuyun. Her $a \to b$ a \to b kenarını $g$ grafına, ters $b \to a$ b \to a kenarını ise $g r$ grafına ekleyin.

scanf("%d %d", &n, &m);
g.resize(n + 1);
gr.resize(n + 1);
for(i = 1; i <= m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  gr[b].push_back(a);
}

C++

Henüz ziyaret edilmemiş her köşeden giriş grafı üzerinde bir derinlik öncelikli arama başlatın. Bundan sonra, $t o p$ dizisi grafın tüm köşelerini işlenmelerinin tamamlanma sırasıyla içerir.

used.resize(n+1);
for(i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

İkinci dolaşımdan önce, $u se d$ dizisini sıfırlayın. Ters grafın köşeleri, işlenmelerinin tamamlanma sırasının tersi sırayla ele alınmalıdır, yani $t o p$ dizisi sondan başa doğru taranmalıdır. Kolaylık olması için, $t o p$ dizisini tersine çevirin.

used.assign(n + 1, 0);
reverse(top.begin(), top.end());

$c$ değişkeni, güçlü bağlantılı bileşenlerin sayısını sayar.

c = 0;

$t o p$ dizisi boyunca soldan sağa hareket edin. Henüz ziyaret edilmemiş her $v$ köşesinden, ters graf üzerinde $df s 2$ derinlik öncelikli aramasını başlatın. Bu, tam olarak bir yeni güçlü bağlantılı bileşeni dolaşır, bu yüzden $c$ 'yi $1$ artırın.

for (int v : top)
  if (!used[v])
  {
    dfs2(v);
    c++;
  }

Grafın güçlü bağlantılı bileşenlerinin sayısını yazdırın.

printf("%d\n",c);

Java uygulaması

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g, gr;
  static boolean used[];
  static Vector<Integer> top = new Vector<Integer>();

  static void dfs1(int v)
  {
    used[v] = true;
    for(int i = 0; i < g[v].size(); i++)
    {
      int to = g[v].get(i);
      if (!used[to]) dfs1(to);
    }
    top.add(v);
  }

  static void dfs2(int v)
  {
    used[v] = true;
    for(int i = 0; i < gr[v].size(); i++)
    {
      int to = gr[v].get(i);
      if (!used[to]) dfs2(to);
    }
  }

  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();

    g = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
    gr = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      gr[i] = new ArrayList<Integer>();

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a].add(b);
      gr[b].add(a);
    }
    used = new boolean[n+1];
    for(int i = 1; i <= n; i++)
      if (!used[i]) dfs1(i);

    used = new boolean[n+1];
    int c = 0;
    for(int i = 1; i <= n; i++)
    {
      int v = top.get(n-i);
      if (!used[v])
      {
        dfs2(v);
        c++;
      }
    }

    System.out.println(c);
    con.close();
  }
}

Java

Python uygulaması

def dfs1(v):
  global g, used, top
  used[v] = True
  for to in g[v]:
    if not used[to]: dfs1(to)
  top.append(v)

def dfs2(v):
  global gr, used
  used[v] = True
  for to in gr[v]:
    if not used[to]: dfs2(to)

Programın ana bölümü. Giriş grafını okuyun. Her $a \to b$ a \to b kenarını $g$ grafına, ters $b \to a$ b \to a kenarını ise $g r$ grafına ekleyin.

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
gr = [[] for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)
  gr[b].append(a)

Python

Henüz ziyaret edilmemiş her köşeden giriş grafı üzerinde bir derinlik öncelikli arama başlatın. Bundan sonra, $t o p$ listesi grafın tüm köşelerini işlenmelerinin tamamlanma sırasıyla içerir.

used = [False] * (n + 1)
top = []
for i in range(1, n + 1):
  if not used[i]: dfs1(i)

İkinci dolaşımdan önce, $u se d$ listesini sıfırlayın. Ters grafın köşeleri, işlenmelerinin tamamlanma sırasının tersi sırayla ele alınmalıdır, bu yüzden $t o p$ listesini tersine çevirin.

used = [False] * (n + 1)
top.reverse()

$c$ değişkeni, güçlü bağlantılı bileşenlerin sayısını sayar.

c = 0

$t o p$ listesi boyunca soldan sağa hareket edin. Henüz ziyaret edilmemiş her $v$ köşesinden, ters graf üzerinde $df s 2$ derinlik öncelikli aramasını başlatın. Bu, tam olarak bir yeni güçlü bağlantılı bileşeni dolaşır, bu yüzden $c$ 'yi $1$ artırın.

for v in top:
  if not used[v]:
    dfs2(v)
    c += 1

Grafın güçlü bağlantılı bileşenlerinin sayısını yazdırın.

print(c)