Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Strongly Connected Components

Hard · Graphs · Asked at Amazon, Google, Microsoft, Samsung

In a directed graph, a strongly connected component is a maximal set of nodes where every node can reach every other. Print the number of strongly connected components.

Input

First line: n m. Next m lines: u v — an edge from u to v.

Output

The number of SCCs.

Constraints

Kosaraju: DFS to get finishing order, reverse all edges, then DFS in decreasing finish time — each new DFS is one SCC. Tarjan's algorithm does it in one pass.

Example 1

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

3

Example 2

Input

3 3
1 2
2 3
3 1

Output

1

Hints

  1. Kosaraju: first DFS records nodes in order of finishing time.
  2. Reverse every edge, then run DFS from nodes in decreasing finishing time; each DFS on the reversed graph visits exactly one SCC.

Approach

Pass 1: iterative DFS on the original graph pushing each node onto order when it finishes. Pass 2: on the reversed graph, take nodes from the end of order (latest finish first); each unvisited one starts a new component and a DFS marks everything it reaches. The node that finishes last lies in a "source" SCC of the condensation, and reversing edges stops the second DFS from leaking into other components. Iterative DFS avoids stack overflow for 10^5 nodes.

Complexity: O(n + m) time · O(n + m) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1), rg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    vector<int> order, it(n + 1, 0);
    vector<bool> seen(n + 1, false);
    for (int s = 1; s <= n; s++) {
        if (seen[s]) continue;
        stack<int> st;
        st.push(s);
        seen[s] = true;
        while (!st.empty()) {
            int u = st.top();
            if (it[u] < (int)g[u].size()) {
                int v = g[u][it[u]++];
                if (!seen[v]) seen[v] = true, st.push(v);
            } else {
                order.push_back(u);
                st.pop();
            }
        }
    }
    vector<int> comp(n + 1, 0);
    int c = 0;
    for (int i = n - 1; i >= 0; i--) {
        int s = order[i];
        if (comp[s]) continue;
        c++;
        stack<int> st;
        st.push(s);
        comp[s] = c;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            for (int v : rg[u])
                if (!comp[v]) comp[v] = c, st.push(v);
        }
    }
    cout << c << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
g = [[] for _ in range(n + 1)]
rg = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    g[u].append(v)
    rg[v].append(u)
seen, order, it = [False] * (n + 1), [], [0] * (n + 1)
for s in range(1, n + 1):
    if seen[s]:
        continue
    seen[s] = True
    stack = [s]
    while stack:
        u = stack[-1]
        if it[u] < len(g[u]):
            v = g[u][it[u]]
            it[u] += 1
            if not seen[v]:
                seen[v] = True
                stack.append(v)
        else:
            order.append(stack.pop())
comp, c = [0] * (n + 1), 0
for s in reversed(order):
    if comp[s]:
        continue
    c += 1
    comp[s] = c
    stack = [s]
    while stack:
        u = stack.pop()
        for v in rg[u]:
            if not comp[v]:
                comp[v] = c
                stack.append(v)
print(c)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<List<Integer>> g = new ArrayList<>(), rg = new ArrayList<>();
        for (int i = 0; i <= n; i++) { g.add(new ArrayList<>()); rg.add(new ArrayList<>()); }
        for (int i = 0; i < m; i++) {
            in.nextToken();
            int u = (int) in.nval;
            in.nextToken();
            int v = (int) in.nval;
            g.get(u).add(v);
            rg.get(v).add(u);
        }
        int[] it = new int[n + 1], order = new int[n];
        int cnt = 0;
        boolean[] seen = new boolean[n + 1];
        int[] st = new int[n + 1];
        for (int s = 1; s <= n; s++) {
            if (seen[s]) continue;
            int top = 0;
            st[top++] = s;
            seen[s] = true;
            while (top > 0) {
                int u = st[top - 1];
                if (it[u] < g.get(u).size()) {
                    int v = g.get(u).get(it[u]++);
                    if (!seen[v]) { seen[v] = true; st[top++] = v; }
                } else {
                    order[cnt++] = u;
                    top--;
                }
            }
        }
        int[] comp = new int[n + 1];
        int c = 0;
        for (int i = n - 1; i >= 0; i--) {
            int s = order[i];
            if (comp[s] != 0) continue;
            c++;
            int top = 0;
            st[top++] = s;
            comp[s] = c;
            while (top > 0) {
                int u = st[--top];
                for (int v : rg.get(u))
                    if (comp[v] == 0) { comp[v] = c; st[top++] = v; }
            }
        }
        System.out.println(c);
    }
}

Solve Strongly Connected Components online · All practice problems