双连通缩点 POJ 1515

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0

1

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
2

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#

题意:已知一堆双向边，要求把尽可能多的双向边改成单向边，但任意两点仍然可以互相到达。

解题思路：除割边需要双向，其他的边按dfs顺序即可。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014/1/18 18:59:49
File Name :F.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=2222;
int head[maxn],tol,low[maxn],dfn[maxn],Stack[maxn],indexx,top,n;
int mp[maxn][maxn];
int vis[maxn];
struct node 
{
      int next,to,cut,xiang;
}edge[300000];
void add(int u,int v)
{
      edge[tol].to=v;
      edge[tol].cut=-1;
      edge[tol].next=head[u];
      head[u]=tol++;
}
void tarjin(int u,int pre)
{
      low[u]=dfn[u]=++indexx;
      Stack[top++]=u;
      int v;
      for(int i=head[u];i!=-1;i=edge[i].next)
      {
	     int v=edge[i].to;
	     if(v==pre)continue;
	     if(edge[i].cut!=-1)continue;
	     edge[i].cut=1;
	     edge[i^1].cut=0;
	     if(!dfn[v])
	     {
		    tarjin(v,u);
		    if(low[u]>low[v])
			   low[u]=low[v];
                  if(low[v]>dfn[u])
		    {
			   edge[i].cut=1;
			   edge[i^1].cut=1;
		    }
	     }
	     else if(low[u]>dfn[v])
		    low[u]=dfn[v];
      }
}
int main()
{
      //freopen("data.in","r",stdin);
      //freopen("data.out","w",stdout);
      int i,j,k,m;
      int ncase=0;
      while(~scanf("%d%d",&n,&m))
      {
	     if(n==0&&m==0)break;
	     memset(head,-1,sizeof(head));
	     tol=0;
	     while(m--)
	     {
		    scanf("%d%d",&i,&j);
		    add(i,j);
		    add(j,i);
	     }
	     printf("%d\n\n",++ncase);
	     memset(dfn,0,sizeof(dfn));
	     indexx=top=0;
	     for(i=1;i<=n;i++)
		    if(!dfn[i])tarjin(i,i);
	     for(i=0;i<tol;i++)if(edge[i].cut==1)printf("%d %d\n",edge[i^1].to,edge[i].to);
	 
	     puts("#");
      }
      return 0;
}

双连通缩点 POJ 1515

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18458939