连通分量：对于一个有向图，一个分量中任意两点u, v，必然可以从u走到v，从v走到u
强连通分量：极大连通分量。

应用：

将有向图通过缩点变为有向无环图(DAG)，即拓扑图。然后再做其它操作。

求解：

DFS的顺序，将所有边分为四大类

  • 树枝边(x -> y，x是y的父节点)
  • 前向边(x -> y，x是y的祖先节点)
  • 横向边(x -> y，y是之前搜过的其它分支上的节点)
  • 后向边(x -> y，y是x的祖先节点)

判断当前节点x是否在某个强连通分量(SCC)中？
情况1：存在一条后向边指向x的祖先节点。
情况2：先走一条横向边，再走到x的祖先节点。
无论哪种情况，能成环的都是当前点的祖先节点。相当于一条后向边直至祖先节点。
如果当前点有一条横向边到达一个未在栈中的点，说明走到了死胡同。

Tarjan算法求强连通分量(SCC)
引入时间戳的概念(dfs过程中的自然数)，对于每个点来说，记录两个时间戳
dfn[u]表示遍历到u节点的时间戳
low[u]表示从u开始走能遍历到的最小时间戳。
如果u是其所在的强连通分量的最高点，等价于dfn[u] == low[u]

缩点：
遍历每条边，找到两个端点所在的强连通分量，如果不是同一个SCC，说明这两个强连通分量之间有一条边。

Tarjan算法执行完后，按照强连通分量编号scc_count从大到小的顺序就是缩点后的图的拓扑序。
为什么呢？因为dfs求拓扑序(dfs遍历每一个点的所有临点，然后将当前点加入队列)的结果就是队列的逆序。而Tarjan添加每一个强连通分量就是按照dfs从小到大添加的，所以其逆序就是拓扑排序。

AcWing 1174. 受欢迎的牛

板子

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 10010, M = 50010;
  5.     static int[] h = new int[N], e = new int[M], ne = new int[M];
  6.     static int idx;
  7.     static int[] dfn = new int[N], low = new int[N];
  8.     static int time_cnt;
  9.     static int[] stk = new int[N];
  10.     static int p = -1;
  11.     static boolean[] in_stk = new boolean[N];
  12.     static int[] id = new int[N], size = new int[N];
  13.     static int scc_cnt;
  14.     static int n, m;
  15.     static int[] dout = new int[N];
  16.     public static void main(String[] args) {
  17.         Scanner sc = new Scanner(System.in);
  19.         n = sc.nextInt();
  20.         m = sc.nextInt();
  21.         Arrays.fill(h, -1);
  22.         for (int i = 0; i < m; i++) {
  23.             int a = sc.nextInt(), b = sc.nextInt();
  24.             add(a, b);
  25.         }
  27.         for (int i = 1; i <= n; i++) {
  28.             if (dfn[i] == 0) {
  29.                 tarjan(i);
  30.             }
  31.         }
  34.         for (int i = 1; i <= n; i++) {
  35.             for (int j = h[i]; j != -1; j = ne[j]) {
  36.                 int k = e[j];
  37.                 int a = id[i], b = id[k];
  38.                 if (a != b) {
  39.                     dout[a]++;
  40.                 }
  41.             }
  42.         }
  44.         int cnt = 0, sum = 0;
  45.         for (int i = 1; i <= scc_cnt; i++) {
  46.             if (dout[i] == 0) {
  47.                 cnt++;
  48.                 sum += size[i];
  49.                 if (cnt > 1) {
  50.                     sum = 0;
  51.                     break;
  52.                 }
  53.             }
  55.         }
  56.         System.out.println(sum);
  57.     }
  59.     static void tarjan(int u) {
  60.         dfn[u] = low[u] = ++time_cnt;
  61.         stk[++p] = u;
  62.         in_stk[u] = true;
  64.         for (int i = h[u]; i != -1; i = ne[i]) {
  65.             int j = e[i];
  66.             if (dfn[j] == 0) 
  67.             {
  68.                 tarjan(j);
  69.                 low[u] = Math.min(low[u], low[j]);
  70.             } 
  71.             else if (in_stk[j]) {
  72.                 low[u] = Math.min(low[u], dfn[j]);
  73.             }
  74.         }
  76.         if (dfn[u] == low[u]) {
  77.             int y;
  78.             ++scc_cnt;
  79.             do {
  80.                 y = stk[p--];
  81.                 in_stk[y] = false;
  82.                 id[y] = scc_cnt;
  83.                 size[scc_cnt]++;
  84.             } while (y != u);
  85.         }
  86.     }
  88.     static void add(int a, int b) {
  89.         e[idx] = b;
  90.         ne[idx] = h[a];
  91.         h[a] = idx++;
  92.     }
  93. }

应用

AcWing 367. 学校网络
结论：缩点后的拓扑图至少加几条边才能变成一个强连通分量？
若本身就是一个强连通分量，加0条边就可以
若本身不是，统计入度为0的缩点的个数c1和出度为0的缩点的个数c2，需要加的边数等于max(c1, c2)

AcWing 1175. 最大半连通子图
强连通分量 + DP

AcWing 368. 银河
同糖果，之前用差分约束 + spfa
这次用强连通分量解决
tarjan缩点 -> 建缩点图 -> 拓扑序处理最长路 -> 遍历求和