图论（连通性问题）

fk-thank / 2023-08-08 / 原文

割点

割点针对于连通图（无向图）。在一张连通图中，如果删去一个点会导致图不连通，那么这个点就是割点。

一般求割点都会使用tarjan算法，这个算法最重要的两个数组分别是 $ dfn $ 和 $ low $ 。

$dfn$ 代表时间戳数组，而$low$数组代表从某点出发回溯到最早的时间戳，也就是走不通过父亲的道路能到达的最小的$dfn$ 。

想要求割点的话只需要考虑两种情况。

第一种：是显而易见的，如果一个节点为搜索树（注意不是图）的根节点，并且有至少2个的子树，那么它就是割点。

证明：因为是搜索树，所以两个子树就代表着它们只能靠根节点来连通，如果删去它，就无法连通了。

第二种：假设一个节点$u$不是根节点,它的儿子为$v$,如果 $ low_v ≥ dfn_u $ ，就说明$u$为割点。

证明：因为 $ low_v ≥ dfn_u $，说明了儿子节点$v$通过回溯无法到达$u$节点之前的已遍历节点。如果删去节点$u$，那么$v$就无法与那些已遍历节点连通。

另外就是tarjan算法的求解问题了，$dfn$数组很容易得出。只需要一个编号赋值就可以了。$low$数组求解的本质是通过dfs来求的，初始时赋值为时间戳，也就是最开始只能回溯到本身。

然后从根节点开始，不断递归，如果递归到未遍历的节点，就用它的$low$取最小值$low[u]=min(low[u],low[v])$

如果遇到一条返祖边，也就是连向已遍历节点的边，取最小值就和前面不太一样了，是$low[u]=min(low[u],dfn[v])$。

因为$u$的$low$数组如果不是本身的时间戳，就一定是其他的儿子节点更新的，假设$u$为割点的话，那么儿子$v$的$low$值肯定不能从其他子树节点的值来更新，因为割点$u$删除就不连通了。自己画图模拟一下就能理解了。

$code:$

#include<bits/stdc++.h>
using namespace std;

const int N = 6e6+5;
int n,m,cnt=1,dfn[N],low[N],id;
int to[N],nxt[N],head[N],ans,root;
bool b[N];

void add(int u,int v){
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void tarjan(int now,int in){
    dfn[now] = low[now] = ++id;
    int son = 0;
    for(int i = head[now] ; i ; i = nxt[i]){
        if(i == (in ^ 1)) continue;
        int g = to[i];
        if(!dfn[g]){
            tarjan(g,i);      son++;
            low[now] = min(low[now],low[g]);
            if(low[g] >= dfn[now] && now != root){
                b[now] = 1;
            }
        }
        else if(i != (in ^ 1))
            low[now] = min(low[now] , dfn[g]);
    }
    if(now == root && son >= 2){
        b[now] = 1;
    }
}

signed main(){
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= m ; ++i ){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i = 1 ; i <= n ; ++i )
        if(!dfn[i]) root = i,tarjan(i,0);
    for(int i = 1 ; i <= n ; ++i )
        if(b[i])  ans++;
    printf("%d\n",ans);
    for(int i = 1 ; i <= n ; ++i )
        if(b[i])  printf("%d ",i);
}

点双连通分量

定义：

点双连通图：一张无向图，任意两个点都可以有两条点不相交的路径到达。也就是一张连通图中没有割点

点双连通分量：选择一个点集使之是一个点双连通图

注意，点双连通分量不满足传递性（强连通分量和边双连通分量是满足的）

因为假设a和b之间没有割点， b和c之间没有割点，那么a和c之间是不一定没有割点的，因为b本身可能就是割点

求解同样使用tarjan算法，过程与割点大部分是一样的。两个点双的公共点只有一个，那就是割点。因为两个点双如果合并为1个就存在割点了。如果是不是割点的话，与之相连的两个点双就要合并为一个。

不是割点的节点只能出现在一个点双里。在dfs的过程中，不断将搜索到的点压入栈中。

如果找到一个割点或者树根，就将栈中找到割点的子树中的节点弹出。如果一颗子树没有找到割点，那就先存在栈里，直到向上找到另外的割点再弹出，注意割点是不能弹出的，因为这个割点还可以算入其他点双中。

树根也要算入点双，如果根节点只有一个子树，那么它肯定要算入儿子节点的点双中。如果有多个子树，那么它也是一个割点。

上述过程实在是不清晰，下面用图具体说明一下

对于这张连通图，他的搜索树其实也是这个样。那么先看3号节点，他的第一个子树显然无法得出3是割点，那就先存入栈中。回溯到1号节点时，和3号以及8号一并归入1号节点的点双中，而7号节点已经因为找到割点而被弹出了。

$ code：$

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5, M = 4e6 + 5;
int cnt = 1, head[N], nxt[M], to[M] , root;
int s[M], top, tot, low[N], dfn[N], id, n, m;
vector<int> ans[N];

void tarjan(int u, int in) {
	int son = 0;
	low[u] = dfn[u] = ++id;
	s[++top] = u;
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
            if(i == (in^1)) continue;
			son++;
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
				tot++;
				while(s[top + 1] != v) ans[tot].push_back(s[top--]);
				ans[tot].push_back(u);
			}
		} else if(i != (in ^ 1)) low[u] = min(low[u], dfn[v]);
	}
	if(root == u && son == 0) ans[++tot].push_back(u);
}
void add(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}

signed main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);add(v, u);
	}
	for(int i = 1; i <= n; i++) {
		if(!dfn[i]){
            top = 0;root = i;
            tarjan(i, 0);
        }
	}
	printf("%d\n", tot);
	for(int i = 1; i <= tot; i++) {
		cout<<ans[i].size()<<" ";
		for(int j = 0 ; j < ans[i].size() ; ++j ) 
            printf("%d ", ans[i][j]);
		printf("\n");
	}
}