无向图的双连通分量

边双连通分量

/*
无向图的边双连通分量(e-DCC)及缩点 
若一张无向图不存在桥,则称这张图为边双连通图
极大边双连通图称为边双连通分量
求法：
用链式前向星存图方便标记边 
找出原图中所有的桥,将桥去掉后形成的各个连通块
即为边双连通分量 
最后缩点就把双连通分量缩为一个点即可 
*/

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 5e4 + 5;

struct edges{
	int to,next; 
}edge[600005];

int cntx = 0;
int head[maxn];

void add(int x,int y)
{
	edge[cntx].to = y;
	edge[cntx].next = head[x];
	head[x] = cntx++;
}

int dfn[maxn],low[maxn];
bool bridge[600005];
int dcc[maxn],cnt = 0,c = 0;  //dcc[i]表示i在第几个边双连通图中 

void tarjan(int x,int in_edge)   //判桥  
{
	dfn[x] = low[x] = cnt ++;
	for (int i = head[x]; i != -1; i = edge[i].next)
	{
		int t = edge[i].to;
		if( !dfn[t] )   
		{
			tarjan(t,i);
			low[x] = min(low[x],low[t]);    
			if( low[t] > dfn[x] )  
			{
				bridge[i] = bridge[i^1] = true;  
			} 
		}else if( i != ( in_edge ^ 1 ) ) low[x] = min(low[x],dfn[t]); 	 
	}
}

void dfs(int x)    //搜索来判断每个点所在的边双连通图 
{
	dcc[x] = c;
	for (int i = head[x]; i != -1; i = edge[i].next)
	{
		int y = edge[i].to;
		if( dcc[y] || bridge[i] ) continue;    //跳过桥
		dfs(y); 
	}
} 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	memset(head,-1,sizeof(head));
	for (int i = 1; i <= m; i++)
	{
		int x,y;
		cin >> x >> y;
		if( x == y ) continue; 
		add(x,y),add(y,x);
	} 
	for (int i = 1; i <= n; i++)
	{
		if( !dfn[i] ) tarjan(i,i);
	}
	for (int i = 1; i <= n; i++)
	{
		if( !dcc[i] )
		{
			c ++;
			dfs(i);
		}
	}
	cout << c << '\n';
 	return 0;
}

点双连通分量

/*
无向图的点双连通分量
注意： 
孤立点也算一个双连通分量
一个割点可能在多个双连通分量中
计算过程：
在tarjan过程中维护一个栈
1.当一个节点第一次被访问时,把该节点入栈
2.当发现这个点x为割点时,无论是否为根,都要执行以下操作
(1)从栈顶不断弹出节点,直至y节点(x的儿子节点)被弹出
(2)弹出的所有节点与x节点一起构成一个v-DCC 
*/ 

#include <iostream>
#include <vector>
using namespace std;

const int maxn = 5e4 + 5;

//由于割点可能出现在多个点强连通分量中,所以我们不能按原来的方式标记每个点 
vector<int> g[maxn],dcc[maxn];  //存点强连通分量 
int cnt = 1,top = 0,c = 0;
int dfn[maxn],low[maxn],sta[maxn]; 
int check[maxn];   

void tarjan(int x,int fa)    //当前节点和连通块的根节点 
{
	dfn[x] = low[x] = cnt ++;
	sta[++top] = x;   //x入栈
	if( x == fa && g[x].size() == 0 )  //孤立点 
	{
		dcc[++c].push_back(x);
		return;
	}
	int child = 0;
	for (int i = 0; i < g[x].size(); i++)
	{
		int t = g[x][i];
		if( !dfn[t] )    //如果这个点之前没被访问,即儿子节点 
		{
			tarjan(t,fa);
			low[x] = min(low[x],low[t]);    //t节点能到的x一定能通过t节点到达 
			if( low[t] >= dfn[x] )  //儿子节点无法通过别的边到达比x小的点,那么说明x为割点 
			{
				child ++; 
				if( x != fa || child > 1 ) check[x] = 1;
				c ++;
				int z;   //找到满足的,执行以下操作,出栈直到t出栈 
				do {
					z = sta[top--];
					dcc[c].push_back(z);
				}while( z != t );
				dcc[c].push_back(x);
			} 
		}
		low[x] = min(low[x],dfn[t]); 
		 //x可以到t,但是不可以由t再到达别的点
		 //若t为x的父节点,并不影响结果,因为有等于。
		 //若t不为x的父节点,那么t一定为x的祖先节点
		 //那么就无法根据x判断其父节点是否为割点,更新到祖先节点即可		 
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if( !dfn[i] ) tarjan(i,i);
	}
	for (int i = 1; i <= c; i++)
	{
		for (int j = 0; j < dcc[i].size(); j++)
		{
			cout << dcc[i][j];
			if( j == dcc[i].size() - 1 ) cout << '\n';
			else cout << ' ';
		}
	} 
	return 0;
}

点双连通分量的缩点

/*
点双连通分量的缩点
由于一个割点属于多个v-dcc
所以我们把每个v-dcc和每个割点都作为新图的节点
并在每个割点与包含它的所有v-dcc之间连边 
*/

#include <iostream>
using namespace std;

int new_id[maxn];
vector<int> new_g[maxn];

void compress(int n)
{
	int num = c;
	for (int i = 1; i <= n; i++)
	{
		if( check[i] ) new_id[i] = ++num;  //给割点新的编号 
	}
	for (int i = 1; i <= c; i++)   //遍历点双连通块 
	{ 
		for (int j = 0; j < dcc[i].size(); j++)  
		{
			int x = dcc[i][j];
			if( check[x] )    //如果x是割点 
			{
				new_g[new_id[x]].push_back(i);  //割点与包含其的连通块相连 
				new_g[i].push_back(new_id[x]);
			}
		}
	}
}