Skip to content

Strongly Connected Components

Introduction

Before reading the following content, please be sure to understand the basics in Graph Theory Concepts.

A directed graph G is said to be strongly connected if every pair of vertices in G is connected.

A Strongly Connected Component (SCC) is defined as a maximal strongly connected subgraph.

Here we will introduce how to find strongly connected components.

Tarjan's Algorithm

Introduction

Robert E. Tarjan (born 1948 in Pomona, California, USA) is a computer scientist.

Tarjan has invented many algorithms and data structures. Many of the algorithms he invented are named after him, which sometimes leads to confusion between different algorithms. For example, Tarjan's algorithm for finding various connected components, and Tarjan's algorithm for finding the LCA (Lowest Common Ancestor). Disjoint Set Union, Splay, and Toptree were also invented by Tarjan.

Here we will introduce Tarjan's algorithm for finding strongly connected components in directed graphs.

DFS Spanning Tree

Before introducing the algorithm, let's understand the DFS Spanning Tree. We take the following directed graph as an example:

DFS Spanning Tree

The DFS spanning tree of a directed graph mainly has four types of edges (not all necessarily appear):

  1. Tree edge: Shown as black edges in the diagram. Each time the search finds a vertex that has not been visited, a tree edge is formed.
  2. Back edge: Shown as red edges in the diagram (e.g., \(7 \rightarrow 1\)), also called a backward edge, which points to an ancestor vertex.
  3. Cross edge: Shown as blue edges in the diagram (e.g., \(9 \rightarrow 7\)). It occurs when the search encounters a vertex that has already been visited, but this vertex is not an ancestor of the current vertex.
  4. Forward edge: Shown as green edges in the diagram (e.g., \(3 \rightarrow 6\)). It is formed when the search encounters a vertex in the subtree.

We consider the relationship between the DFS spanning tree and strongly connected components.

If vertex \(u\) is the first vertex encountered in a DFS tree that belongs to a certain strongly connected component, then all other vertices of that strongly connected component must be in the subtree rooted at \(u\) in the DFS tree. Vertex \(u\) is called the root of this strongly connected component.

Proof by contradiction: Suppose there is a vertex \(v\) in this strongly connected component but not in the subtree rooted at \(u\). Then the path from \(u\) to \(v\) must contain an edge that leaves the subtree. However, such edges can only be cross edges or back edges, both of which require the pointed vertex to have already been visited. This contradicts the assumption that \(v\) is not in the subtree rooted at \(u\). Q.E.D.

Tarjan's Algorithm for Finding Strongly Connected Components

Tarjan's algorithm is based on performing a Depth-First Search on the graph. We view each connected component as a subtree in the DFS tree. During the search, we maintain a stack, adding each unprocessed node in the DFS tree to the stack.

In Tarjan's algorithm, the following variables are maintained for each vertex \(u\):

  1. \(\textit{dfn}_u\): The order in which vertex \(u\) is visited during the depth-first search traversal.
  2. \(\textit{low}_u\): The earliest vertex in the stack that can be reached from the subtree of \(u\) by backtracking. Let the subtree rooted at \(u\) be \(\textit{Subtree}_u\). \(\textit{low}_u\) is defined as the minimum \(\textit{dfn}\) among the following vertices: vertices in \(\textit{Subtree}_u\); vertices reachable from \(\textit{Subtree}_u\) via an edge not in the DFS tree.

The dfn values of vertices in a vertex's subtree are all greater than that vertex's dfn.

Along a path from the root, dfn strictly increases, and low is strictly non-decreasing.

Following the order of the depth-first search, we search all vertices in the graph, maintain the dfn and low variables for each vertex, and push visited vertices onto the stack. Whenever a strongly connected element is found, we pop elements from the stack according to the number of vertices contained in that element. During the search, for vertex \(u\) and its adjacent vertex \(v\) (where \(v\) is not the parent of \(u\)), we consider three cases:

  1. \(v\) is unvisited: Continue the depth-first search on \(v\). During backtracking, update \(\textit{low}_u\) with \(\textit{low}_v\). Because there is a direct path from \(u\) to \(v\), any vertex that \(v\) can backtrack to that is already in the stack, \(u\) can also backtrack to.
  2. \(v\) has been visited and is in the stack: According to the definition of low, update \(\textit{low}_u\) with \(\textit{dfn}_v\).
  3. \(v\) has been visited and is no longer in the stack: This means \(v\) has been fully processed, and its connected component has been handled, so no operation is needed.

The above algorithm can be written in pseudocode as follows:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been searched then
            TARJAN_SEARCH(v) // search
            low[u]=min(low[u],low[v]) // backtrack
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

For a connected component graph, it is easy to see that there is exactly one \(u\) such that \(\textit{dfn}_u=\textit{low}_u\). This vertex must be the first vertex visited in this connected component during the depth-first traversal, because its dfn and low values are the smallest and are not affected by other vertices in the same connected component.

Therefore, during backtracking, we check if \(\textit{dfn}_u=\textit{low}_u\) holds. If it does, then the vertices from \(u\) to the top of the stack form an SCC.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // The SCC id of vertex i
int sz[N];       // Size of SCC i

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    do {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
    } while (s[tp--] != u);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
dfn = [0] * N
low = [0] * N
dfncnt = 0
s = [0] * N
in_stack = [0] * N
tp = 0
scc = [0] * N
sc = 0  # The SCC id of vertex i
sz = [0] * N  # Size of SCC i


def tarjan(u):
    low[u] = dfn[u] = dfncnt
    s[tp] = u
    in_stack[u] = 1
    dfncnt = dfncnt + 1
    tp = tp + 1
    i = h[u]
    while i:
        v = e[i].t
        if dfn[v] == False:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif in_stack[v]:
            low[u] = min(low[u], dfn[v])
        i = e[i].nex
    if dfn[u] == low[u]:
        sc = sc + 1
        while s[tp] != u:
            scc[s[tp]] = sc
            sz[sc] = sz[sc] + 1
            in_stack[s[tp]] = 0
            tp = tp - 1
        scc[s[tp]] = sc
        sz[sc] = sz[sc] + 1
        in_stack[s[tp]] = 0
        tp = tp - 1

Time complexity: \(O(n + m)\).

Relationship Between Component Labeling and Topological Order

During its processing, Tarjan's algorithm essentially discovers strongly connected components in a kind of reverse topological order. This is because the algorithm, during its depth-first search, visits nodes without outgoing edges first, which is the opposite of the topological sorting process.

If we contract all strongly connected components in the graph into single nodes, then performing a topological sort on the resulting DAG (Directed Acyclic Graph) of contracted nodes will yield an order that is the reverse of the labeling order given by Tarjan's algorithm for the strongly connected components.

Therefore, it can be said that in the contracted DAG, the labeling order of the strongly connected components (after contraction) is the reverse of their topological order. However, note that this statement holds only when considering the dependency relationships between strongly connected components (i.e., directed edges from one SCC to another). The nodes within a single SCC, due to the presence of cycles, do not satisfy the definition of a topological order internally.

Kosaraju's Algorithm

Introduction

Kosaraju's algorithm was first proposed by S. Rao Kosaraju in an unpublished paper in 1978, but it was first published by Micha Sharir.

Process

This algorithm relies on two simple DFS passes:

First DFS: Start from any vertex, traverse all unvisited vertices, and assign a number to each vertex before backtracking, i.e., perform a post-order traversal.

Second DFS: For the reversed graph, start DFS from the vertex with the largest label. The set of vertices visited in this DFS forms one strongly connected component. For all unvisited vertices, pick the one with the largest label and repeat the above process.

After the two DFS passes, the strongly connected components are found. The time complexity of Kosaraju's algorithm is \(O(n+m)\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// g is the original graph, g2 is the reversed graph

void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) dfs1(v);
  s.push_back(u);
}

void dfs2(int u) {
  color[u] = sccCnt;
  for (int v : g2[u])
    if (!color[v]) dfs2(v);
}

void kosaraju() {
  sccCnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);
  for (int i = n; i >= 1; --i)
    if (!color[s[i]]) {
      ++sccCnt;
      dfs2(s[i]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def dfs1(u):
    vis[u] = True
    for v in g[u]:
        if vis[v] == False:
            dfs1(v)
    s.append(u)


def dfs2(u):
    color[u] = sccCnt
    for v in g2[u]:
        if color[v] == False:
            dfs2(v)


def kosaraju(u):
    sccCnt = 0
    for i in range(1, n + 1):
        if vis[i] == False:
            dfs1(i)
    for i in range(n, 0, -1):
        if color[s[i]] == False:
            sccCnt = sccCnt + 1
            dfs2(s[i])

Garbow's Algorithm

Process

Garbow's algorithm is another implementation of Tarjan's algorithm. While Tarjan's algorithm uses dfn and low to compute the root of a strongly connected component, Garbow's algorithm maintains a node stack and uses a second stack to determine when to pop nodes belonging to the same SCC from the first stack. During a DFS starting from node \(w\), when a path indicates that a set of nodes all belong to the same SCC, nodes are popped from the second stack as long as the top node's visit time is greater than the root node \(w\)'s visit time, leaving only the root node \(w\) in the end. Every node popped during this process belongs to the same SCC.

When backtracking to a node \(w\), if this node is at the top of the second stack, it indicates that this node is the starting node of a strongly connected component. All nodes searched after this node belong to the same SCC, so we pop those nodes from the first stack to form the SCC.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int garbow(int u) {
  stack1[++p1] = u;
  stack2[++p2] = u;
  low[u] = ++dfs_clock;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!low[v])
      garbow(v);
    else if (!sccno[v])
      while (low[stack2[p2]] > low[v]) p2--;
  }
  if (stack2[p2] == u) {
    p2--;
    scc_cnt++;
    do {
      sccno[stack1[p1]] = scc_cnt;
      // all_scc[scc_cnt] ++;
    } while (stack1[p1--] != u);
  }
  return 0;
}

void find_scc(int n) {
  dfs_clock = scc_cnt = 0;
  p1 = p2 = 0;
  memset(sccno, 0, sizeof(sccno));
  memset(low, 0, sizeof(low));
  for (int i = 1; i <= n; i++)
    if (!low[i]) garbow(i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def garbow(u):
    stack1[p1] = u
    stack2[p2] = u
    p1 = p1 + 1
    p2 = p2 + 1
    low[u] = dfs_clock
    dfs_clock = dfs_clock + 1
    i = head[u]
    while i:
        v = e[i].to
        if low[v] == False:
            garbow(v)
        elif sccno[v] == False:
            while low[stack2[p2]] > low[v]:
                p2 = p2 - 1
    if stack2[p2] == u:
        p2 = p2 - 1
        scc_cnt = scc_cnt + 1
        while stack1[p1] != u:
            p1 = p1 - 1
            sccno[stack1[p1]] = scc_cnt


def find_scc(n):
    dfs_clock = scc_cnt = 0
    p1 = p2 = 0
    sccno = []
    low = []
    for i in range(1, n + 1):
        if low[i] == False:
            garbow(i)

Applications

We can contract each strongly connected component of a graph into a single vertex.

Then the graph becomes a DAG, on which we can perform topological sorting and many other operations.

For a simple example, find a path that can pass through repeated vertices, requiring the maximum number of distinct vertices visited.

Exercises

USACO Fall/HAOI 2006 Popular Cows

POJ1236 Network of Schools

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用