POJ 1515 无向连通图定向边改造为强连通 边双连通

题意：

n个点m条无向边（保证图连通）

问：把尽量多的无向边定向，使得最终图保持强连通的特性。

输出：

案例数

最终图的所有单向边 ( 若是不能被定向的无向边则输出u,v && v,u表示2条无向边 )

#

思路：

显然桥是不能被定向的，双连通求出桥。

去掉桥后，对于每个连通分支，可以dfs遍历一遍把经过的边定向，这样一定保证连通分量是强连通的。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#define N 1005
#define M 1000005
using namespace std;

int n,m;//n个点 m条边
struct node
{
	int from,to,nex;
	int cut;//记录这条边是否为割边 
}edge[2*M];//双向边则 edge[i]与edge[i^1]是2条反向边
int head[N] ,edgenum;//在一开始就要 memset(head,-1,sizeof(head)); edgenum=0;
int low[N],dfn[N],tarjin_time;
void add(int u,int v)
{
	node E={u,v,head[u],0};
	edge[edgenum]=E;
	head[u]=edgenum++;
}
void tarjin(int u,int pre)
{
	low[u]=dfn[u]= ++tarjin_time;
	int flag=1;//flag是阻止双向边的反向边 i和i^1
	for(int i=head[u];i!=-1;i=edge[i].nex)
	{
		int v=edge[i].to;
		if(flag&&v==pre)
		{
			flag=0;
			continue;
		}
		if(!dfn[v])
		{
			tarjin(v,u);
			if(low[u]>low[v])low[u]=low[v];
			if(low[v]>dfn[u])//是桥low[v]表示v能走到的最早祖先 有重边且u是v的最早祖先 则low[v]==dfn[u],所以不会当作桥
				edge[i].cut=edge[i^1].cut=true;
		}
		else if(low[u]>dfn[v])low[u]=dfn[v];
	}
}
bool liantong;//是否连通
void find_edgecut()
{
	memset(dfn,0,sizeof(dfn));
	tarjin_time=0;
	tarjin(1,1);
	liantong=true;
	for(int i=1;i<=n;i++)if(!dfn[i]){liantong=false;return;}
}
bool vis[N];
void init(){
	for(int i = 0;i<=n;i++)head[i] = -1;
	edgenum = 0;
	memset(vis, 0, sizeof(vis));
}

void dfs(int u, int fa){
	vis[u] = true;
	for(int i = head[u]; ~i; i = edge[i].nex){
		int v = edge[i].to;
		if( edge[i].cut == 1)continue;
		if(edge[i^1].cut!=-1)edge[i].cut = -1;
		if(!vis[v])	dfs(v, u);
	}
}
int main(){
	int u, v, Cas = 1;
	while(scanf("%d %d",&n,&m), n+m){
		init();
		while(m--){
			scanf("%d %d", &u, &v);
			add(u, v);
			add(v, u);
		}
		find_edgecut();
		for(int i = 1; i <= n; i++)if(!vis[i])dfs(i, i);
		printf("%d\n\n", Cas++);
		for(int i = 0; i < edgenum; i++)if(edge[i].cut)printf("%d %d\n", edge[i].from, edge[i].to);
		puts("#");
	}
	return 0;
}

POJ 1515 无向连通图定向边改造为强连通 边双连通

原文：http://blog.csdn.net/acmmmm/article/details/18263421