Tarjan系列算法解决各种连通性问题。

图的连通性

有向图的连通性

算法流程稍复杂，细节很多。

难点在于缩点之后做什么，为什么答案是这样，猜出或者证明出需要统计的答案的表达式比较困难

有向图的极大强连通子图叫做强连通分量

求强连通分量能把有向图转化为有向无环图

有向无环图有优秀的性质：有向无环图可以拓扑排序，可以做dp、递推

按照dfs的顺序求强连通分量

图中的四类边：

• 树枝边，是搜索树中的边
• 前向边(x,y)，在搜索树中x是y的祖先
• 后向边（反之，一定是向上走）
• 横叉边，在图中横叉边总是指向“左”，指向“右”的边会在dfs中马上被搜到

存在后向边指向祖先节点时存在一个强连通分量（直接走到某个祖先）

存在横叉边，然后横叉边可以走到祖先节点（间接走到某个祖先）

时间戳：

dfn[u]遍历到u的时间

low[u]，从u开始走所能够遍历到的最小的时间戳

u是某个强连通分量中的最高点等价于dfn[u] = low[u]（即不能够再往上走了）

下面是个错的板子

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    s[++top] = u, instack[u] = true;
    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        int j = edge[i].to;
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (instack[j]){
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scccnt;
        int t;
        do {
            t = s[top--];
            instack[t] = false;
            id[t] = scccnt;
        } while (u != t);
    }
}

缩点：遍历所有点，遍历所有邻边，如果x,y不在同一个连通块，就在id(x)和id(y)之间加一条边

连通分量编号递减的顺序就是拓扑序

有时候缩点没有必要显式建出来新的图

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 9;
const int M = 5e4 + 9;

vector<int> g[N];
stack<int> s;
int dfn[N], low[N], id[N], sz[N], timestamp = 0;
int outdeg[N];
bool vis[N], instack[N];
int n, m, scc_cnt = 0;

void tarjan(int u) {
    vis[u] = true;
    instack[u] = true;
    s.push(u);
    dfn[u] = low[u] = ++timestamp;
    int size = g[u].size();
    for (int i = 0; i < size; i++) {
        int j = g[u][i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (instack[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;
        do {
            v = s.top();
            s.pop();
            id[v] = scc_cnt;
            instack[v] = false;
            sz[scc_cnt]++;
        } while (u != v);
    } 
}

int main() {
    int x, y;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            tarjan(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        int size = g[i].size();
        for (int j = 0; j < size; j++) {
            int u = g[i][j];
            if (id[i] != id[u]) {
                outdeg[id[i]]++;
            }
        }
    }
    int cnt = 0, ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!outdeg[i]) {
            cnt++;
            ans += sz[i];
            if (cnt > 1) {
                ans = 0;
                break;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

无向图的连通性

类似强连通分量，无向图拥有双连通分量，分为边双连通分量和点双连通分量。

边双连通分量

基本概念

桥：如果无向图中存在一条边，删去该边之后整个图不再连通，那么这条边叫做桥。

边双连通分量：极大的不含有桥的连通子图叫做边双连通分量。

边双连通分量的几条简单的性质：

• 由于边双连通分量不存在桥，所以不管删掉边双中的哪条边都能保证分量连通。
• 一个图是边双等价于该图的任意两点之间存在至少两条不包括公共边的路径。
• 树上的每条边都是桥；按照边双对图进行缩点之后所有的边都是桥。通过加边使得树中没有度为1的点，即可使得得到的图为边双。

桥的判定

我们仍然采用上面求强连通分量的dfn, low的定义。

考虑一条边(x, y)，从x遍历到y，y是还没有访问过的点。

• 倘若dfn[x] < low[y] ，就意味着y结点不可能回溯到x以及x的上方，所以如果删除(x, y)，那么图必然不会连通。所以这个时候(x, y)就是桥。
• 倘若dfn[x] >= low[y]，那么意味着y能够回溯到x甚至更上面，那么删除(x, y)也不影响x和y的连通性，图当然还是连通的，所以这个时候不是桥。

如果使用的是链式前向星存图的话，我们可以使用一个bool数组标记一下哪些边是桥。

如果x是从边from到达的，那么在从x走向别的点的时候，不能再走from的反边!

重边？

可以画图模拟一下，如果能走反边的话，那么我可以刚走完(x, y)就走(y, x)，用x更新y，对于每个点都这么办，那么最后在原图上连通的所有的low[x]都是相等的，这样就判不出来桥了。

求边双

有两种思路：

• 删除所有的桥，则剩下的都是边双。
• 利用类似求强连通分量的做法，使用栈来存储边双中的点。

对于第二种思路，仍然以dfn[u] == low[u]作为该点是边双“顶点”的标志（因为这个时候说明u最多只能回溯到他自己，所以u就是顶点）。

缩点

如果判断桥的时候已经完成了标记桥，且求边双的时候求得了每个结点归属于哪个边双，那么缩点只需要遍历一遍全图，如果id[x] != id[y]，则连接一条无向边(id[x], id[y])即可。当然，根据题目的要求，我们有时候可能可以不把缩点之后的图建出来，只需要统计缩点之后的图的一些信息即可。

按照边双进行缩点之后，会形成森林（如果原来的图是连通的，那么得到的就是树）。

代码模板

void tarjan(int u, int from) {
    // from是u的入边
    dfn[u] = low[u] = ++timestamp;
    s.push(u);

    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        int j = edge[i].to;
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            // 桥的判定条件
            if (dfn[u] < low[j]) {
                isbridge[i] = isbridge[i ^ 1] = true;
            }
        } else if (i != (from ^ 1)) {
            // 不能够用父亲的时间戳更新孩子的时间戳
            low[u] = min(low[u], dfn[j]);
        }
    }

    // 边双顶点的判定条件
    if (dfn[u] == low[u]) {
        dcc_cnt++;
        int v;
        do {
            v = s.top();
            s.pop();
            id[v] = dcc_cnt;
        } while (v != u);
    }
}

点双连通分量

基本概念

割点：如果把无向图中某个点及其边删去之后图变得不连通，那么这个点叫做割点。

点双连通分量：TODO

割点和点双的几条简单的性质与常见误解：

• 每个割点在缩点时至少属于两个点双。
• 两个割点之间的边不一定是桥。
• 桥的两个端点不一定是割点。（点双和边双没有本质关联）

割点的判定

感性思考一下，目前有一条边(x, y)，从x走到y，类似边双，考虑dfn[x]和low[y]的关系。若dfn[x] <= low[y] ，那么说明y只能回溯到x或者x的下面，那么，删去x之后，似乎y和其他的部分没法连通了。可是，倘若x为根节点，且只和y相连，那么事实上剩下的部分还是连通的，所以并不能简单的只看dfn[x]和low[y]的关系，还要考虑x是否是根节点。倘若x真的是根节点，那么，什么时候x才是割点呐？显然需要其有至少两个“孩子”y1, y2，满足dfn[x] <= low[y1] && dfn[x] <= low[y2]，这样才能保证删除x之后整个图不再连通。

综上，判断割点是这样做的：

考虑边(x, y)，从x走到y

• 若x是“根节点”，则当至少存在两个“孩子”y1, y2，满足dfn[x] <= low[y1] && dfn[x] <= low[y2]时，x是割点。
• 若x不是“根节点”，则当dfn[x] <= low[y]时，x是割点。

在代码实现时，遍历从x出发的所有出边的时候，可以考虑统计满足dfn[x] <= low[y]的y的个数，最后根据是否为根节点以及统计结果判断x是不是割点。

在维护low[x]的时候，如果y是已经访问过的点，一定要用dfn[y]去更新low[x]，否则会导致一些割点找不出来。而在求Scc和e-Dcc 时，使用low[y]和dfn[y]是一样的。可以画图模拟一下。

在判定割点的时候，走入边的反向边是不影响结果的。因为走反向边的时候，刷新时为low[x] = min(low[x], dfn[y]) ，倘若本来low[x] <= dfn[y]，那没啥；倘若low[x] > dfn[y]，且不存在其他的小于dfn[y]的可以更新的值了，由于我们最后统计的是有多少小于等于，这样一来至多是小于变成小于等于，不影响结果。

求点双

缩点

代码模板