强连通分量和 Tarjan

强连通分量(Strongly Connected Components，SCC)，指的是极大的连通子图。

tarjan 算法，用于求图的强连通分量。

dfs 生成树

有向图的 dfs 生成树大致分为四种边：

树边(tree edge)：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
反祖边(back edge)：示意图中以红色边表示(即 \(7 \rightarrow 1\))，也被叫做回边，即指向祖先结点的边。
横叉边(cross edge)：示意图中以蓝色边表示(即 \(9 \rightarrow 7\))，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
前向边(forward edge)：示意图中以绿色边表示（即 \(3 \rightarrow 6\))，它是在搜索的时候遇到子树中的结点的时候形成的。

如果结点 \(u\) 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 \(u\) 为根的子树中。结点 \(u\) 被称为这个强连通分量的根。

反证法：假设有个结点 \(v\) 在该强连通分量中但是不在以 \(u\) 为根的子树中，那么 \(u\) 到的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 \(u\) 是第一个访问的结点矛盾了。得证。

Tarjan 求强连通分量

需要对每个节点 \(u\) 都维护以下几个信息：

\(dfn_u\)：\(u\) 在深度优先搜索时是第几个被访问的~~(人称豆腐脑序)~~。
\(low_u\)：在 \(u\) 的子树中能够回溯到的最早的在栈中的结点。

很明显，对于每个 \(u\) 的后代 \(i\) 都有 \(dfn_u < dfn_i\)。从根开始的一条路径上的 \(dfn\) 严格递增，\(low\) 严格非降。

用 dfs 来求 \(dfn\) 和 \(low\)，每搜索到一个新的节点就让它入栈，每找到一个强连通分类，就让它们出栈。

当节点 \(u\) 向节点 \(v\) 做遍历时，有三种情况：

\(v\) 未被访问，则对 \(v\) 进行 dfs，回溯时 low[u] = min(low[u], low[v]); 因为存在从 \(u\) 到 \(v\) 的直接路径，所以 \(v\) 能够回溯到的已经在栈中的结点，\(u\) 也一定能够回溯到。
\(v\) 已被访问且仍在栈中，那么 low[u] = min(low[u], dfn[v]);
\(v\) 被访问过且已不在栈中，说明 \(v\) 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

处理完以后，我们可以想到在一个强连通分量里有且仅有一个点 \(u\) 满足 \(dfn_u=low_u\)，该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 \(dfn\) 和 \(low\) 值最小，不会被该连通分量中的其他结点所影响。

所以只要在回溯的过程中判断 \(dfn_u\) 是否和 \(low_u\) 相等，若相等，则栈内 \(u\) 及它上方的节点构成一个 SCC。

const int N = 1e4 + 10;

int n, dfncnt, dfn[N], low[N], bel[N], stk[N], top, fstk[N], sc, sz[N], b[N], ans, sum, c[N];
vector<int> g[N];

void tarjan (int x) {
  dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
  for (int i : g[x]) {
    if (!dfn[i]) {
      tarjan(i), low[x] = min(low[x], low[i]);
    } else if (fstk[i]) {
      low[x] = min(low[x], dfn[i]);
    }
  }
  if (dfn[x] == low[x]) {
    ++sc;
    while (1) {
      sz[sc]++, fstk[stk[top]] = 0, bel[stk[top--]] = sc;
      if (stk[top + 1] == x) {
        break;
      }
    }
  }
}

应用

我们可以将每个强连通分量都压缩成一个点(缩点)，那么原图就会变成 DAG，可以进行拓扑排序等。

例题

P2746 [USACO5.3] 校园网Network of Schools | #10091. 「一本通 3.5 例 1」受欢迎的牛

割点和割边

割点

对于一个无向图，如果把这个点删除后这个图的极大连通分量数增加了，那么这个点就是原图的割点(割顶)。

举个例子，这张图内的割点明显只有 \(2\)。

首先我们先通过 DFS 给它们打上时间戳：

记录在 \(dfn\) 中，还需要另外一个数组 low，用它来存储不经过其父亲能到达的最小的时间戳。

好，和 Tarjan 扯上关系了，那么首先 Tarjan 预处理一下，可以得到定理：对于某个顶点 \(u\)，如果存在至少一个顶点 \(v\)(\(u\) 的儿子)，使得 \(low_v \geqslant dfn_u\)，即不能回到祖先，那么 \(u\) 点为割点。

但是对于搜索树的根节点需要特殊处理：若该点不是割点，则其他路径亦能到达全部结点，因此从起始点只「向下搜了一次」，即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子，那么他一定是割点了(设想上图从 \(2\) 开始搜索，搜索树内应有两个子结点：\(3\) 或 \(4\) 及 \(5\) 或 \(6\))。如果只有一个儿子，那么把它删掉，不会有任何的影响。比如下面这个图，此处形成了一个环。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10;

int n, m, dfncnt, dfn[N], low[N], bel[N], stk[N], top, fstk[N], sc, sz[N], cnt;
vector<int> g[N];
bool ans[N];

void tarjan (int x, int fa) {
  int son = 0;
  dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
  for (int i : g[x]) {
    if (!dfn[i]) {
      son++;
      tarjan(i, x), low[x] = min(low[x], low[i]);
      if (fa != x && low[i] >= dfn[x] && !ans[x]) {
        ans[x] = 1, cnt++;
      }
    } else if (i != fa) {
      low[x] = min(low[x], dfn[i]);
    }
  }
  if (fa == x && son >= 2 && !ans[x]) {
    ans[x] = 1, cnt++;
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1, x, y; i <= m; i++) {
    cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
      dfncnt = 0, tarjan(i, i);
    }
  }
  cout << cnt << '\n';
  for (int i = 1; i <= n; i++) {
    if (ans[i]) {
      cout << i << ' ';
    }
  }
  return 0;
}

模板题 Link

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图 \(G=\{V,E\}\)，\(e\) 是其中一条边(即 \(e \in E\))，如果 \(G-e\) 是不连通的，则边 \(e\) 是图 \(G\) 的一条割边(桥)。

比如下图中红色边就是割边。

和割点差不多，不需要特殊考虑更根节点，只要把 \(low_v \geqslant dfn_u\) 改为 \(low_v > dfn_u\) 即可。

void tarjan (int x, int fa) {
  int son = 0;
  dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
  for (int i : g[x]) {
    if (!dfn[i]) {
      son++;
      tarjan(i, x), low[x] = min(low[x], low[i]);
      if (low[i] > dfn[x] && !ans[x]) {
        ans[x] = 1, cnt++;
      }
    } else if (i != fa) {
      low[x] = min(low[x], dfn[i]);
    }
  }
}