Strong connectivity#2403

Strong connectivity (Editorial)

The problem requires finding the number of strongly connected components of a directed graph. To do this, we use Kosaraju's algorithm, which performs two depth-first searches:

perform a depth-first search on the input graph and record the vertices in the order in which their processing is finished (at the moment of leaving the vertex);
build the reverse graph by reversing the direction of every edge;
iterate over the vertices in the reverse order of finishing their processing, and start a depth-first search on the reverse graph from every vertex that has not been visited yet. Each such start traverses exactly one strongly connected component.

The reverse graph has the same strongly connected components as the original one: if there are paths from $u$ to $v$ and from $v$ to $u$ , then after reversing the edges these paths are preserved, only their direction changes. The order of processing vertices in the second traversal guarantees that the depth-first search does not leave the current component: all components it could reach have already been visited by this moment.

The answer is the number of depth-first search starts in the second traversal.

Example

The graphs given in the examples are shown below. Strongly connected components are highlighted in color.

The first graph contains no cycles: it is impossible to return to any vertex. Therefore, each vertex forms a separate strongly connected component: ${1}$ , ${2}$ , ${3}$ .

In the second graph, vertices $1$ , $2$ and $3$ lie on the cycle $1 \to 2 \to 3 \to 1$ 1 \to 2 \to 3 \to 1 and form one component ${1, 2, 3}$ \{1, 2, 3\}. Vertex $4$ cannot be reached from vertex $5$ , so vertices $4$ and $5$ form separate components ${4}$ and ${5}$ . Thus, each of the graphs contains $3$ strongly connected components.

Let us simulate the algorithm on the second graph. The first depth-first search from vertex $1$ follows the path $1 \to 2 \to 3$ 1 \to 2 \to 3, and then from vertex $4$ the path $4 \to 5$ 4 \to 5. The order in which vertex processing is finished is $t o p = (3, 2, 1, 5, 4)$ top = (3, 2, 1, 5, 4). After reversing, we get $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3).

The reverse graph contains the edges $2 \to 1$ 2 \to 1, $3 \to 2$ 3 \to 2, $1 \to 3$ 1 \to 3 and $5 \to 4$ 5 \to 4. Perform the second traversal in the order $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3):

$df s 2 (4)$ : vertex $4$ has no outgoing edges in the reverse graph, component ${4}$ ;
$df s 2 (5)$ : the edge $5 \to 4$ 5 \to 4 leads to an already visited vertex, component ${5}$ ;
$df s 2 (1)$ : traverse the path $1 \to 3 \to 2$ 1 \to 3 \to 2, component ${1, 3, 2}$ \{1, 3, 2\}.

Vertices $2$ and $3$ have already been visited, so there are no new starts. We obtain $c = 3$ c = 3 components.

Note that in the reverse graph vertex $4$ , which belongs to another component, is reachable from vertex $5$ . However, vertex $4$ is processed before vertex $5$ , so by the time $df s 2 (5)$ is called it has already been visited and does not get into the component of vertex $5$ .

Algorithm implementation

Store the input graph as an adjacency list $g$ , and the reverse graph as an adjacency list $g r$ . The array $u se d$ marks visited vertices. The array $t o p$ stores the vertices in the order in which their processing is finished during the first depth-first search.

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

The function dfs1 performs a depth-first search on the input graph. Vertex $v$ is appended to the end of the array $t o p$ after all vertices reachable from it have been processed, that is, at the moment of leaving it.

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

C++

The function dfs2 performs a depth-first search on the reverse graph. All vertices visited during one call of $df s 2$ from the main program form one strongly connected component.

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

The main part of the program. Read the input graph. Add each edge $a \to b$ a \to b to the graph $g$ , and the opposite edge $b \to a$ b \to a to the reverse graph $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++

Start a depth-first search on the input graph from every vertex that has not been visited yet. After that, the array $t o p$ contains all vertices of the graph in the order in which their processing was finished.

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

Before the second traversal, reset the array $u se d$ . The vertices of the reverse graph must be considered in the reverse order of finishing their processing, that is, the array $t o p$ must be scanned from the end to the beginning. For convenience, reverse the array $t o p$ .

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

The variable $c$ counts the number of strongly connected components.

c = 0;

Move through the array $t o p$ from left to right. From each vertex $v$ that has not been visited yet, start the depth-first search dfs2 on the reverse graph. It traverses exactly one new strongly connected component, so increase $c$ by $1$ .

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

Print the number of strongly connected components of the graph.

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

Java implementation

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 implementation

The function dfs1 performs a depth-first search on the input graph. Vertex $v$ is appended to the end of the list $t o p$ after all vertices reachable from it have been processed, that is, at the moment of leaving it.

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

The function dfs2 performs a depth-first search on the reverse graph. All vertices visited during one call of $df s 2$ from the main program form one strongly connected component.

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

The main part of the program. Read the input graph. Add each edge $a \to b$ a \to b to the graph $g$ , and the opposite edge $b \to a$ b \to a to the reverse graph $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

Start a depth-first search on the input graph from every vertex that has not been visited yet. After that, the list $t o p$ contains all vertices of the graph in the order in which their processing was finished.

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

Before the second traversal, reset the list $u se d$ . The vertices of the reverse graph must be considered in the reverse order of finishing their processing, so reverse the list $t o p$ .

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

The variable $c$ counts the number of strongly connected components.

c = 0

Move through the list $t o p$ from left to right. From each vertex $v$ that has not been visited yet, start the depth-first search dfs2 on the reverse graph. It traverses exactly one new strongly connected component, so increase $c$ by $1$ .

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

Print the number of strongly connected components of the graph.

print(c)