无向图的双连通分量

边双连通分量

定义：

一个不存在割边的极大连通子图被称为无向图的边双连通分量。这里极大的定义为当前的双连通分量不能再继续扩展一条边，使得当前连通分量不存在割边。

求法：

边双连通分量可以使用 Tarjan 算法 求出，其主要想法是维护每一个点的时间戳，如果当前的某一个点可以到达一个时间戳先于它的点，那么这两个点之间的路径上的所有点几位一个边双连通分量的点，这可以用栈维护。

Code：

以 P8436【模板】边双连通分量为例

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500010, M = 4000010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top, cnt;
vector<int> edcc[N];
int root;

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}

void tarjan(int u, int edge)
{
	dfn[u] = low[u] = ++ timestamp;
	
	if(u == root && h[u] == -1) 
	{
		edcc[++ cnt].push_back(u);
		return;
	}
	
	stk[ ++ top] = u;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int ver = e[i];
		
		if(!dfn[ver]) 
		{
			tarjan(ver, i);
			
			low[u] = min(low[u], low[ver]);
		}
		else if(i != (edge ^ 1)) low[u] = min(low[u], dfn[ver]);
	}
	
	if(dfn[u] == low[u])
	{
		cnt ++ ;
		while(stk[top] != u)
			edcc[cnt].push_back(stk[top -- ]);
		edcc[cnt].push_back(stk[top -- ]);
	}
}

int main()
{
	memset(h, -1, sizeof h);
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		
		if(a == b) continue;
		add(a, b), add(b, a);
	}
	
	for(root = 1; root <= n; root ++ )
	{
		if(dfn[root]) continue;
		tarjan(root, -1);
	}
	
	printf("%d\n", cnt);
	for(int i = 1; i <= cnt; i ++ )
	{
		printf("%lld", edcc[i].size());
		for(auto ver : edcc[i]) printf(" %d", ver);
		printf("\n");
	}
	
	return 0;
}

点双连通分量

定义：

一个不存在割点的极大连通子图被称为无向图的点双连通分量。这里的极大定义为当前的两桶分量不能再扩展一个点，使得当前的两桶分量不存在割点。

求法：

和边双连通分量的求法基本相同，也是 的时间复杂度，但是一个割点可以存在于多个点双连通分量中，所以我们将割点单独拎出来，将其连向包含该点的点双连通分量。

Code：

以 P8435【模板】点双连通分量为例

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500010, M = 4000010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root;
int cnt, stk[N], top;
vector<int> vdcc[N];

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}

void tarjan(int u)
{
	dfn[u] = low[u] = ++ timestamp;
	
	if(root == u && h[u] == -1)
	{
		vdcc[ ++ cnt].push_back(u);
		return;
	}
	
	stk[ ++ top] = u;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int ver = e[i];
		
		if(!dfn[ver])
		{
			tarjan(ver);
			
			low[u] = min(low[u], low[ver]);
			if(dfn[u] <= low[ver])
			{
				cnt ++ ;
				int y;
				do {
					y = stk[top -- ];
					vdcc[cnt].push_back(y);
				} while(y != ver);
				vdcc[cnt].push_back(u);
			}
		}
		else low[u] = min(low[u], dfn[ver]);
	}
}

int main()
{
	memset(h, -1, sizeof h);
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		
		if(a == b) continue;
		add(a, b), add(b, a);
	}
	
	for(root = 1; root <= n; root ++ )
	{
		if(dfn[root]) continue;
		tarjan(root);
	}
	
	printf("%d\n", cnt);
	for(int i = 1; i <= cnt; i ++ )
	{
		printf("%d ", vdcc[i].size());
		for(auto ver : vdcc[i]) printf("%d ", ver);
		printf("\n");
	}
	
	return 0;
}