强连通分量

定义

连通图：图中，任意的两个点互相可达。

强连通(\(strongly\ connected\))：在有向图 \(G\) 中，若两个顶点间至少存在一条路径，称两个顶点强连通。

强连通图：有向图 \(G\) 的任意两个顶点都强连通。

强连通分量(\(strongly\ connected\ components\)，简称 \(SCC\))：非强连通图有向图的极大强连通子图。

通俗的讲，强连通就是两个点互相可达，强连通图就是图种任意两个点互相可达，强连通分量是该图中，任意的一些点都不能和该强连通分量互相可达

弱连通：将有向图 \(G\) 的每条边都看作无向边，若两个顶点间至少存在一条路径，称两个顶点弱连通。

弱连通图：有向图 \(G\) 的任意两个顶点都弱连通。

如下图，\(\{A,F,G\}\)，\(\{B,C,D\}\)，\(\{E\}\) 是三个强连通分量

Tarjan 算法

\(Tarjan\) 算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

\(Tarjan\) 算法维护了两个变量：

1. \(DFN_u\)：在深度优先搜索下，节点 \(u\) 的访问次序编号
2. \(LOW_u\)：\(u\) 或 \(u\) 的子树能够追溯到的最早的栈中节点的次序编号

在回溯时，若 \(DFN_u=LOW_u\)，则以 \(u\) 为根的搜索子树上的所有节点是一个强连通分量。

算法伪代码

tarjan(u)
{
	DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
	Stack.push(u)                              // 将节点u压入栈中
	for each (u, v) in E                       // 枚举每一条边
		if (v is not visted)               // 如果节点v未被访问过
			tarjan(v)                  // 继续向下找
			Low[u] = min(Low[u], Low[v])
		else if (v in S)                   // 如果节点v还在栈内
			Low[u] = min(Low[u], DFN[v])
	if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
		while (u != v)
			v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
			print v
		S.pop						// 自己出栈
		print u
}

具体例子，如下图

\(Tarjan\) 算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为 \(O(N+M)\)。

Java语言 \(Tarjan\) 求强连通分量代码

import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {

    // n 个节点，标号为 0~n
    // m 条有向边
    static int n, m;
    // 邻接表存图
    static List<Integer>[] adj;
    // DFS的搜索次序数
    static int time;
    // dfn 为 DFS序， low 为能回溯到的最早的 dfn
    static int[] dfn, low;
    // 栈的"指针"
    static int top = -1;
    // stack 数组模拟栈
    static int[] stack;
    // inStack 判断 i 是否在栈中
    static boolean[] inStack;
    // 强连通分量个数
    static int cnt;
    // 节点 i 属于哪个强连通分量
    static int[] belong;

    static void tarjan(int u) {
        dfn[u] = low[u] = ++time;
        stack[++top] = u;
        inStack[u] = true;
        for (Integer v : adj[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                continue;
            }
            if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            ++cnt;
            int t = stack[top];
            while (t != u) {
                belong[t] = cnt;
                inStack[t] = false;
                t = stack[--top];
            }
            belong[u] = cnt;
            inStack[u] = false;
            --top;
        }
    }


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        adj = new LinkedList[n];
        for (int i = 0; i < n; ++i) adj[i] = new LinkedList<Integer>();
        dfn = new int[n];
        low = new int[n];
        stack = new int[n];
        inStack = new boolean[n];
        belong = new int[n];
        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt(), v = sc.nextInt();
            adj[u].add(v);
        }
        tarjan(0);
        System.out.printf("该有向图有 %d 个强连通分量%n", cnt);
        for (int i = 0; i < n; ++i) {
            System.out.printf("%d 号节点在强连通分量 %d 中%n", i, belong[i]);
        }
    }
}

测试输入数据：
7 9
0 1
1 2
2 3
3 4
2 4
3 1
0 5
5 6
6 0
测试输出数据：
该有向图有 3 个强连通分量
0 号节点在强连通分量 3 中
1 号节点在强连通分量 2 中
2 号节点在强连通分量 2 中
3 号节点在强连通分量 2 中
4 号节点在强连通分量 1 中
5 号节点在强连通分量 3 中
6 号节点在强连通分量 3 中

例题

P2863 The Cow Prom S - 洛谷

不一定是连通图，因此需要对每个未遍历到的节点进行 \(tarjan\)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.List;

public class Main {

    // n 个节点，标号为 0~n
    // m 条有向边
    static int n, m;
    // 邻接表存图
    static List<Integer>[] adj;
    // DFS的搜索次序数
    static int time;
    // dfn 为 DFS序， low 为能回溯到的最早的 dfn
    static int[] dfn, low;
    // 栈的"指针"
    static int top = -1;
    // stack 数组模拟栈
    static int[] stack;
    // inStack 判断 i 是否在栈中
    static boolean[] inStack;
    // 强连通分量个数
    static int cnt;
    // 第 i-1 个强连通分量内节点个数
    static int[] scc;

    static void tarjan(int u) {
        dfn[u] = low[u] = ++time;
        stack[++top] = u;
        inStack[u] = true;
        for (Integer v : adj[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                continue;
            }
            if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            int t = stack[top];
            while (t != u) {
                ++scc[cnt];
                inStack[t] = false;
                t = stack[--top];
            }
            inStack[u] = false;
            --top;
            ++scc[cnt];
            ++cnt;
        }
    }

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int get() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        n = get();
        m = get();
        adj = new LinkedList[n];
        for (int i = 0; i < n; ++i) adj[i] = new LinkedList<Integer>();
        dfn = new int[n];
        low = new int[n];
        stack = new int[n];
        inStack = new boolean[n];
        scc = new int[n];
        for (int i = 0; i < m; ++i) adj[get() - 1].add(get() - 1);
        for (int i = 0; i < n; ++i) {
            if (dfn[i] == 0) tarjan(i);
        }
        int ans = 0;
        for (int i = 0; i < cnt; ++i) {
            if (scc[i] > 1) ++ans;
        }
        System.out.println(ans);
    }
}

参考资料

有向图强连通分量的Tarjan算法 (byvoid.com)

强连通分量 - OI Wiki

轻松掌握tarjan强连通分量_哔哩哔哩