无向图的边双连通分量

无向图边双连通分量：对于一个无向图，任意两点之间至少存在两条边不重复的路径，则图是双连通的；边双连通的极大子图为边双连通分量；

求解边双连通分量：

1、dfs找出所有的桥；

2、把桥边删除，原图形成多个连通块，每个连通块就是一个边双连通分量；（只需再次dfs不经过桥就行）；

poj3352 求边双连通分量；

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<map>
#define ll long long
#define MAX 1010
#define INF INT_MAX
#define eps 1e-8

using namespace std;

struct Edge{
	int from,to;
};

vector<int>G[MAX];
vector<Edge>edges;

int pre[MAX],low[MAX],iscut[MAX][MAX],c[MAX],dfs_clock,n;

void init(){
	for (int i = 0; i<=n; i++) G[i].clear();
	edges.clear();
	memset(iscut,0,sizeof(iscut));
	memset(pre,0,sizeof(pre));
	memset(c,0,sizeof(c));
	dfs_clock = 0;
}

int dfs(int u, int fa){
	int lowu = pre[u] = ++dfs_clock;
	for (int i=0; i<G[u].size(); i++){
		int v = G[u][i];
		if (!pre[v]){
			int lowv = dfs(v,u);
			lowu = min(lowu,lowv);
			if (lowv > pre[u]){       //标记桥
				iscut[u][v]  = iscut[v][u] = 1;
				edges.push_back((Edge){u,v});
			}
		}
		else if (pre[v] < pre[u] && v != fa){
			lowu = min(lowu,pre[v]);
		}
	}
	low[u] = lowu;
	return lowu;
}

int bcc[MAX],cnt;

void dfs1(int u){       //求边双连通分量
	if (bcc[u]) return;
	bcc[u] = cnt;
	for(int i=0; i<G[u].size(); i++){
		int v = G[u][i];
		if (iscut[u][v]) continue;
		dfs1(v);
	}
}

int main(){
	int m;
	while (scanf("%d%d",&n,&m) != EOF){
		int u,v;
		init();
		for (int i=0; i<m; i++){
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(1,-1);
	//	for (int i=0; i<edges.size(); i++) printf("%d  %d\n",edges[i].from,edges[i].to);
		memset(bcc,0,sizeof(bcc));
		cnt = 0;
		for (int i=1; i<=n; i++){
			if (!bcc[i]){
				cnt++;
				dfs1(i);
			}
		}
	//	printf("\n");
	//	for (int i=1; i<=n; i++) printf("%d ",bcc[i]); printf("\n");
		for (int i=0; i<edges.size(); i++){
			int x = edges[i].from;
			int y = edges[i].to;
			c[bcc[x]]++;
			c[bcc[y]]++;
		}
		int ans = 0;
		for (int i=1; i<=cnt; i++) if (c[i] == 1) ans++;
		printf("%d\n",(ans+1) / 2);
	}
	return 0;
}


           

这个题需要用到的命题：
           

一颗树有n（n>=2）个叶子节点的树，至少（只需）添加(n+1)/2条边，才（就）能转化为没有桥的图。或者说，使得图中 的每条边都至少在一个环上；