【学习笔记】无向图的连通性

· · 算法·理论

割点

定义： 在无向图连通图中，若把点 x 删去后整个图就不连通了，则 x 为割点（割顶）。

朴素方法： 每次删去一个点，然后判断图是否连通，时间复杂度为 O(n(n+m))。

Tarjan 算法：

$low_x$：在 $x$ 及以后被搜索的所有节点的 $low$ 值和这些节点能到达的节点的 $dfn$ 的最小值。 **算法流程：** 1. 从 $1$ 号点开始遍历全图，对于遍历到的点 $x$，记录它的 $dfn_x$ 并将 $low_x$ 的值赋为 $dfn_x$。 2. 接下来遍历 $x$ 的所有子儿子 $y$： - 若 $y$ 被访问过，则 $low_x=\min(low_x,dfn_y)$。 - 若 $y$ 没有被访问过，则先遍历 $y$，接着 $low_x=\min(low_x,low_y)$。 **算法原理：** 若点 $x$ 不为割点，把所有没被访问过 $y$ 放在 $x$ 的“下方”，则必存在一条边从 $y$ 连到 $x$ 的“上方”且这条边在 $x$ 的“右边”（不然应该先访问到这条边，或者说访问顺序在 $x$ 之后），按照 $low$ 数组的定义，则所以的 $y$ 都满足 $low_y<dfn_x$。 相反，若 $x$ 为割点，则必有 $low_y\ge dfn_x$（注意，这里有等于号，因为若连到自己则仍为割点）。 **特例：** 若 $x$ 为根节点，则肯定存在 $low_y\ge dfn_x$，判断不出割点，需要特判一下：如果 $x$ 连接的联通块个数 $\ge 2$，则其断开后这几个联通块会分开，则 $x$ 为割点。 ```cpp void tarjan(int k, int rt) { int cnt = 0; dfn[k] = low[k] = ++s; for (auto i : p[k]) { if (!dfn[i]) { cnt++; tarjan(i, rt); low[k] = min(low[k], low[i]); if (k != rt && low[i] >= dfn[k]) { if (!flag[k]) ans++; flag[k] = true; } } else low[k] = min(low[k], dfn[i]); } if (k == rt && cnt > 1) { if (!flag[k]) ans++; flag[k] = true; } } ``` **时间复杂度：**$O(n+m)

割边

定义： 在无向连通图中，若删去某条边，这个图就不连通了，则称这条边是割边（桥）。

Tarjan 算法：

求割边的算法与求割点的算法差不多，只是如果一条从 x 到 y 的边为割边，则 y 不存在边能到 y 节点及其“上方”，即存在 y 使 low_y>dfn_x（这里和割点有所区别）。

代码实现时要注意，这里的边是双向边，为了每条边只访问一次，可以使用邻接链表来存图，这样在边表中一条边 e 的反向边为 e\oplus1，注意这样存图边的编号得从 2 开始。

void tarjan(int k) {
    int cnt = 0;
    dfn[k] = low[k] = ++s;
    for (int i = head[k]; i; i = e[i].nxt) {
        if (vis[i]) continue;
        vis[i] = vis[i ^ 1] = true;
        if (!dfn[e[i].to]) {
            tarjan(e[i].to);
            low[k] = min(low[k], low[e[i].to]);
            if (low[e[i].to] > dfn[k])
                bri[i] = bri[i ^ 1] = true;
        }
        else low[k] = min(low[k], dfn[e[i].to]);
    }
}

时间复杂度：O(n+m)

点双连通分量（v-Dcc）

定义： 无向图中极大的（不能往外扩张）不存在割点的连通图（割点是指“局部”的割点），其任意两点之间都存在不经过重复点的两条路径。

性质： 一个割点可以存在于多个点双连通分量中，非割点只能存在于一个点双连通分量中，否则其就不是“分量”。

求法： 同样是 Tarjan 算法，不过要开一个栈记录：遍历到 x 时便把 x 压入栈，若 x 为割点，则它通过当前点“吊”着的所有点都弹出（x 不弹出），而 x 则是由“吊”着它的点弹出。有个注意点，到 y 时只应弹出 y 吊着的这一串，而不是把 x 吊的所有点都弹出。

特例： 当 x 为孤立点时，它自成一个点双连通分量。

void tarjan(int k) {
    q.push(k);
    dfn[k] = low[k] = ++s;
    int sum = 0;
    for (auto i : p[k]) {
        if (!dfn[i]) {
            sum++;
            tarjan(i);
            low[k] = min(low[k], low[i]);
            if (low[i] >= dfn[k]) {
                cnt++;
                int t;
                do {
                    t = q.top();
                    ans[cnt].push_back(q.top());
                    q.pop();
                }while (t != i);
                ans[cnt].push_back(k);
            }
        }
        else low[k] = min(low[k], dfn[i]);
    }
    if (k == rt && sum == 0) ans[++cnt].push_back(k);
}

时间复杂度：O(n+m)

边双连通分量

定义： 无向图中极大的（不能往外扩张）不存在割边的连通图，其任意两点之间都存在不经过重复边的两条路径。

性质： 割边可以不存在于任何边双连通分量中，非割边只能存在于一个边双连通分量中。

求法： 由于边双连通分量中不包含割边，那么就可以先跑一遍 Tarjan 标记出割边，然后 dfs，不经过割边跑出的联通块就是边双连通分量。

//省略 Tarjan 函数
void dfs(int k)
{
    ans[sum].push_back(k);
    vis[k] = true;
    for (int i = head[k]; i; i = e[i].nxt)
    {
        if (bri[i]) continue;
        int v = e[i].to;
        if (!vis[v]) dfs(v); 
    }
}

练习题

\color{#9D3DCF}\texttt{SP2878 KNIGHTS - Knights of the Round Table}

\color{#3498DB}\texttt{P3469 [POI2008] BLO-Blockade}

\color{#3498DB}\texttt{P2860 [USACO06JAN] Redundant Paths G}