Güclü əlaqəlilik#2403

Güclü əlaqəlilik (Həll təhlili)

Məsələdə yönlü qrafın güclü bağlı komponentlərinin sayını tapmaq tələb olunur. Bunun üçün iki dərinliyinə axtarış yerinə yetirən Kosaraju alqoritmindən istifadə edirik:

giriş qrafı üzərində dərinliyinə axtarış yerinə yetirin və təpələri emalının başa çatdığı ardıcıllıqla qeyd edin (təpədən çıxan anda);
hər kənarın istiqamətini tərsinə çevirməklə tərs qraf qurun;
təpələri emalının başa çatma ardıcıllığının tərsinə doğru keçin və hələ ziyarət edilməmiş hər təpədən tərs qraf üzərində dərinliyinə axtarışa başlayın. Belə hər bir başlanğıc dəqiq bir güclü bağlı komponenti gəzir.

Tərs qrafın ilkin qrafla eyni güclü bağlı komponentləri var: əgər $u$ -dan $v$ -yə və $v$ -dən $u$ -ya yollar varsa, onda kənarlar tərsinə çevrildikdən sonra bu yollar qorunur, yalnız onların istiqaməti dəyişir. İkinci gəzintidə təpələrin emal ardıcıllığı dərinliyinə axtarışın cari komponentdən kənara çıxmamasını təmin edir: onun çata biləcəyi bütün komponentlər bu anadək artıq ziyarət edilmişdir.

Cavab ikinci gəzintidə dərinliyinə axtarışın başlanğıc sayıdır.

Misal

Misallarda verilmiş qraflar aşağıda göstərilmişdir. Güclü bağlı komponentlər rənglə qeyd olunub.

Birinci qraf heç bir dövr saxlamır: hər hansı təpəyə qayıtmaq mümkün deyil. Buna görə də hər təpə ayrıca güclü bağlı komponent təşkil edir: ${1}$ , ${2}$ , ${3}$ .

İkinci qrafda $1$ , $2$ və $3$ təpələri $1 \to 2 \to 3 \to 1$ 1 \to 2 \to 3 \to 1 dövrü üzərində yerləşir və bir komponent ${1, 2, 3}$ \{1, 2, 3\} təşkil edir. $4$ təpəsinə $5$ təpəsindən çatmaq mümkün olmadığından, $4$ və $5$ təpələri ayrı ${4}$ və ${5}$ komponentlərini təşkil edir. Beləliklə, hər bir qrafda $3$ güclü bağlı komponent var.

İkinci qraf üzərində alqoritmi simulyasiya edək. $1$ təpəsindən birinci dərinliyinə axtarış $1 \to 2 \to 3$ 1 \to 2 \to 3 yolunu, sonra isə $4$ təpəsindən $4 \to 5$ 4 \to 5 yolunu izləyir. Təpələrin emalının başa çatma ardıcıllığı $t o p = (3, 2, 1, 5, 4)$ top = (3, 2, 1, 5, 4) olur. Tərsinə çevirdikdən sonra $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3) alırıq.

Tərs qraf $2 \to 1$ 2 \to 1, $3 \to 2$ 3 \to 2, $1 \to 3$ 1 \to 3 və $5 \to 4$ 5 \to 4 kənarlarını ehtiva edir. İkinci gəzintini $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3) ardıcıllığı ilə yerinə yetirək:

$df s 2 (4)$ : $4$ təpəsinin tərs qrafda çıxan kənarı yoxdur, komponent ${4}$ ;
$df s 2 (5)$ : $5 \to 4$ 5 \to 4 kənarı artıq ziyarət edilmiş təpəyə aparır, komponent ${5}$ ;
$df s 2 (1)$ : $1 \to 3 \to 2$ 1 \to 3 \to 2 yolunu gəzir, komponent ${1, 3, 2}$ \{1, 3, 2\}.

$2$ və $3$ təpələri artıq ziyarət edildiyindən, yeni başlanğıc yoxdur. Biz $c = 3$ c = 3 komponent alırıq.

Qeyd edək ki, tərs qrafda başqa komponentə aid olan $4$ təpəsinə $5$ təpəsindən çatmaq mümkündür. Lakin $4$ təpəsi $5$ təpəsindən əvvəl emal edildiyindən, $df s 2 (5)$ çağırıldığı anda o artıq ziyarət edilmiş olur və $5$ təpəsinin komponentinə düşmür.

Alqoritmin reallaşdırılması

Giriş qrafı qonşuluq siyahısı $g$ kimi, tərs qrafı isə qonşuluq siyahısı $g r$ kimi saxlayırıq. $u se d$ massivi ziyarət edilmiş təpələri işarələyir. $t o p$ massivi birinci dərinliyinə axtarış zamanı təpələrin emalının başa çatma ardıcıllığını saxlayır.

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

dfs1 funksiyası giriş qrafı üzərində dərinliyinə axtarış yerinə yetirir. $v$ təpəsi ondan əlçatan bütün təpələr emal edildikdən sonra, yəni ondan çıxan anda $t o p$ massivinin sonuna əlavə olunur.

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

C++

dfs2 funksiyası tərs qraf üzərində dərinliyinə axtarış yerinə yetirir. Əsas proqramdan $df s 2$ -nin bir çağırışı zamanı ziyarət edilən bütün təpələr bir güclü bağlı komponent təşkil edir.

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

Proqramın əsas hissəsi. Giriş qrafını oxuyun. Hər $a \to b$ a \to b kənarını $g$ qrafına, əks $b \to a$ b \to a kənarını isə $g r$ tərs qrafına əlavə edin.

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++

Giriş qrafı üzərində hələ ziyarət edilməmiş hər təpədən dərinliyinə axtarışa başlayın. Bundan sonra $t o p$ massivi qrafın bütün təpələrini emalının başa çatma ardıcıllığı ilə ehtiva edir.

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

İkinci gəzintidən əvvəl $u se d$ massivini sıfırlayın. Tərs qrafın təpələri emalının başa çatma ardıcıllığının tərsinə baxılmalıdır, yəni $t o p$ massivi sondan əvvələ doğru taranmalıdır. Rahatlıq üçün $t o p$ massivini tərsinə çevirin.

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

$c$ dəyişəni güclü bağlı komponentlərin sayını hesablayır.

c = 0;

$t o p$ massivi üzərində soldan sağa hərəkət edin. Hələ ziyarət edilməmiş hər $v$ təpəsindən tərs qraf üzərində dfs2 dərinliyinə axtarışına başlayın. O, dəqiq bir yeni güclü bağlı komponenti gəzir, buna görə $c$ -ni $1$ artırın.

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

Qrafın güclü bağlı komponentlərinin sayını çap edin.

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

Java reallaşdırılması

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 reallaşdırılması

dfs1 funksiyası giriş qrafı üzərində dərinliyinə axtarış yerinə yetirir. $v$ təpəsi ondan əlçatan bütün təpələr emal edildikdən sonra, yəni ondan çıxan anda $t o p$ siyahısının sonuna əlavə olunur.

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)

Proqramın əsas hissəsi. Giriş qrafını oxuyun. Hər $a \to b$ a \to b kənarını $g$ qrafına, əks $b \to a$ b \to a kənarını isə $g r$ tərs qrafına əlavə edin.

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

Giriş qrafı üzərində hələ ziyarət edilməmiş hər təpədən dərinliyinə axtarışa başlayın. Bundan sonra $t o p$ siyahısı qrafın bütün təpələrini emalının başa çatma ardıcıllığı ilə ehtiva edir.

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

İkinci gəzintidən əvvəl $u se d$ siyahısını sıfırlayın. Tərs qrafın təpələri emalının başa çatma ardıcıllığının tərsinə baxılmalıdır, buna görə $t o p$ siyahısını tərsinə çevirin.

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

$c$ dəyişəni güclü bağlı komponentlərin sayını hesablayır.

c = 0

$t o p$ siyahısı üzərində soldan sağa hərəkət edin. Hələ ziyarət edilməmiş hər $v$ təpəsindən tərs qraf üzərində dfs2 dərinliyinə axtarışına başlayın. O, dəqiq bir yeni güclü bağlı komponenti gəzir, buna görə $c$ -ni $1$ artırın.

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

Qrafın güclü bağlı komponentlərinin sayını çap edin.

print(c)