Indian Computing Olympiad

Advanced graph algorithms

Strongly connected components

In a directed graph, u and v are strongly connected if there is a path from u to v and a path from v to u.

Being strongly connected is an equivalence relation. Strongly connected components are the equivalence classes of this relation. Thus, the set of verticies can be partitioned into strongly connected components (scc's).

How do we compute strongly connected components?

We begin by augmenting dfs to compute two quantities for each vertex:

1. dfsno[v] : the order in which dfs(v) is invoked
2. exitno[v] : the order in which dfs(v) terminates

Pseudo code for dfs:

   d = 0;   // counter for assigning dfsno
   e = 0;   // counter for assigning exitno
   dfs(v) {
     mark v;

     d++; set dfsno[v] = d;

     for each neighbour w of v
        if w is unmarked
           dfs(w);

     e++; exitno[v] = e;
   }
      

Now, suppose we construct a new graph in which

• Vertices : scc's of original graph
• Edge : c1 → c2 if there is an edge in the original graph from some v1 in c1 to some v2 in c2

This new graph is a dag. Observe that if c1→c2 in the scc dag, the max exit number in c1 is bigger than the max exit number in c2.

Suppose we reverse all the edges in the original graph. All the dfs tree edges are reversed.

Now, in the reversed graph, we start a dfs in an scc containing the highest exit number. This dfs cannot leave the scc—this scc has only outgoing edges in the original graph since it has the highest exit number, so in the reversed graph it has only incoming edges. On the other hand, since this is an scc, whether we follow reversed edges or original edges, all vertices in the scc will be reachable by dfs. In other words, the dfs will mark precisely the vertices of this scc.

Now, we look at unmarked vertex with highest exit number. This is in a different scc. Once again, if we start a dfs here, we cannot leave the scc—the only outgoing (reverse) edge can be to an scc before it in the original dag, but that scc is already visited.

In this way, if we start each time with the unmarked vertex that highest exit number, we identify its scc.

This gives the following algorithm for computing scc's:

1. Do a normal dfs and compute exit numbers.

      For v1,v2,...,vn do
        if vi is not marked
          dfs(vi)
   	  

   Let w1,w2,...,wn be list of vertices ordered by descending order of exit number.

2. Reverse the edges in G

      For w1,w2,...,wn do
        if wi is not marked
          dfs(wi)
   	  

Video lecture on Applications of BFS and DFS, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)