Connessione forte#2403

Connessione forte (Editoriale)

Il problema richiede di trovare il numero di componenti fortemente connesse di un grafo diretto. Per fare questo, utilizziamo l'algoritmo di Kosaraju, che esegue due visite in profondità:

eseguire una visita in profondità sul grafo di input e registrare i vertici nell'ordine in cui termina la loro elaborazione (nel momento in cui si lascia il vertice);
costruire il grafo inverso invertendo la direzione di ogni arco;
iterare sui vertici nell'ordine inverso rispetto al termine della loro elaborazione, e avviare una visita in profondità sul grafo inverso a partire da ogni vertice non ancora visitato. Ogni avvio di questo tipo attraversa esattamente una componente fortemente connessa.

Il grafo inverso ha le stesse componenti fortemente connesse del grafo originale: se esistono cammini da $u$ a $v$ e da $v$ a $u$ , allora dopo l'inversione degli archi questi cammini vengono preservati, cambiando solo la loro direzione. L'ordine di elaborazione dei vertici nella seconda visita garantisce che la visita in profondità non esca dalla componente corrente: tutte le componenti che potrebbe raggiungere sono già state visitate a questo punto.

La risposta è il numero di avvii della visita in profondità nella seconda visita.

Esempio

I grafi forniti negli esempi sono mostrati di seguito. Le componenti fortemente connesse sono evidenziate con colori diversi.

Il primo grafo non contiene cicli: è impossibile tornare a un qualsiasi vertice. Pertanto, ogni vertice forma una componente fortemente connessa separata: ${1}$ , ${2}$ , ${3}$ .

Nel secondo grafo, i vertici $1$ , $2$ e $3$ si trovano sul ciclo $1 \to 2 \to 3 \to 1$ 1 \to 2 \to 3 \to 1 e formano un'unica componente ${1, 2, 3}$ \{1, 2, 3\}. Il vertice $4$ non può essere raggiunto dal vertice $5$ , quindi i vertici $4$ e $5$ formano componenti separate ${4}$ e ${5}$ . Pertanto, ciascuno dei grafi contiene $3$ componenti fortemente connesse.

Simuliamo l'algoritmo sul secondo grafo. La prima visita in profondità dal vertice $1$ segue il cammino $1 \to 2 \to 3$ 1 \to 2 \to 3, e poi dal vertice $4$ il cammino $4 \to 5$ 4 \to 5. L'ordine in cui termina l'elaborazione dei vertici è $t o p = (3, 2, 1, 5, 4)$ top = (3, 2, 1, 5, 4). Dopo l'inversione, otteniamo $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3).

Il grafo inverso contiene gli archi $2 \to 1$ 2 \to 1, $3 \to 2$ 3 \to 2, $1 \to 3$ 1 \to 3 e $5 \to 4$ 5 \to 4. Eseguiamo la seconda visita nell'ordine $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3):

$df s 2 (4)$ : il vertice $4$ non ha archi uscenti nel grafo inverso, componente ${4}$ ;
$df s 2 (5)$ : l'arco $5 \to 4$ 5 \to 4 conduce a un vertice già visitato, componente ${5}$ ;
$df s 2 (1)$ : si attraversa il cammino $1 \to 3 \to 2$ 1 \to 3 \to 2, componente ${1, 3, 2}$ \{1, 3, 2\}.

I vertici $2$ e $3$ sono già stati visitati, quindi non ci sono nuovi avvii. Otteniamo $c = 3$ c = 3 componenti.

Si noti che nel grafo inverso il vertice $4$ , che appartiene a un'altra componente, è raggiungibile dal vertice $5$ . Tuttavia, il vertice $4$ viene elaborato prima del vertice $5$ , quindi nel momento in cui viene chiamata $df s 2 (5)$ esso è già stato visitato e non entra a far parte della componente del vertice $5$ .

Implementazione dell'algoritmo

Memorizziamo il grafo di input come lista di adiacenza $g$ , e il grafo inverso come lista di adiacenza $g r$ . L'array $u se d$ segna i vertici visitati. L'array $t o p$ memorizza i vertici nell'ordine in cui termina la loro elaborazione durante la prima visita in profondità.

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

La funzione dfs1 esegue una visita in profondità sul grafo di input. Il vertice $v$ viene aggiunto alla fine dell'array $t o p$ dopo che tutti i vertici raggiungibili da esso sono stati elaborati, cioè nel momento in cui lo si lascia.

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

C++

La funzione dfs2 esegue una visita in profondità sul grafo inverso. Tutti i vertici visitati durante una chiamata di $df s 2$ dal programma principale formano una componente fortemente connessa.

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

Parte principale del programma. Leggiamo il grafo di input. Aggiungiamo ogni arco $a \to b$ a \to b al grafo $g$ , e l'arco opposto $b \to a$ b \to a al grafo inverso $g r$ .

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

Avviamo una visita in profondità sul grafo di input a partire da ogni vertice non ancora visitato. Dopo di ciò, l'array $t o p$ contiene tutti i vertici del grafo nell'ordine in cui è terminata la loro elaborazione.

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

Prima della seconda visita, azzeriamo l'array $u se d$ . I vertici del grafo inverso devono essere considerati nell'ordine inverso rispetto al termine della loro elaborazione, cioè l'array $t o p$ deve essere scorso dalla fine all'inizio. Per comodità, invertiamo l'array $t o p$ .

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

La variabile $c$ conta il numero di componenti fortemente connesse.

c = 0;

Scorriamo l'array $t o p$ da sinistra a destra. Da ogni vertice $v$ non ancora visitato, avviamo la visita in profondità dfs2 sul grafo inverso. Essa attraversa esattamente una nuova componente fortemente connessa, quindi incrementiamo $c$ di $1$ .

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

Stampiamo il numero di componenti fortemente connesse del grafo.

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

Implementazione in Java

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

Implementazione in Python

La funzione dfs1 esegue una visita in profondità sul grafo di input. Il vertice $v$ viene aggiunto alla fine della lista $t o p$ dopo che tutti i vertici raggiungibili da esso sono stati elaborati, cioè nel momento in cui lo si lascia.

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

La funzione dfs2 esegue una visita in profondità sul grafo inverso. Tutti i vertici visitati durante una chiamata di $df s 2$ dal programma principale formano una componente fortemente connessa.

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

Parte principale del programma. Leggiamo il grafo di input. Aggiungiamo ogni arco $a \to b$ a \to b al grafo $g$ , e l'arco opposto $b \to a$ b \to a al grafo inverso $g r$ .

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

Avviamo una visita in profondità sul grafo di input a partire da ogni vertice non ancora visitato. Dopo di ciò, la lista $t o p$ contiene tutti i vertici del grafo nell'ordine in cui è terminata la loro elaborazione.

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

Prima della seconda visita, azzeriamo la lista $u se d$ . I vertici del grafo inverso devono essere considerati nell'ordine inverso rispetto al termine della loro elaborazione, quindi invertiamo la lista $t o p$ .

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

La variabile $c$ conta il numero di componenti fortemente connesse.

c = 0

Scorriamo la lista $t o p$ da sinistra a destra. Da ogni vertice $v$ non ancora visitato, avviamo la visita in profondità dfs2 sul grafo inverso. Essa attraversa esattamente una nuova componente fortemente connessa, quindi incrementiamo $c$ di $1$ .

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

Stampiamo il numero di componenti fortemente connesse del grafo.

print(c)