【题意】
给定一个双向连通的公路网，当某些公路路段检修的时候可能会由于该段公路不通，可能会使某些旅游点之间无法通行，求至少新建多少条公路，使得任意对一段公路进行检修的时候，所有的旅游景点之间仍然畅通。
造成公路不通的原因是图中存在桥，所以题目要求的是添加最少条公路使图中不存在桥。
1 // 3352 Accepted 228K 32MS C++ 1333B 2013-03-07 09:54:55 2 // 利用low[i]缩点 3 #include<stdio.h> 4 #include< string.h> 5 #include<stack> 6 using namespace std; 7 #define N 1005 8 #define M 2010 9 10 int low[N],dfn[N],ins[N],degree[N],fa[N],index,s; 11 struct Edge 12 { 13 int e,next; 14 }edge[M]; 15 int tail[N],eNum; 16 char a[ 10]; 17 stack < int>st; 18 19 int Min( int x, int y) 20 { 21 if(x>y) return y; 22 return x; 23 } 24 void Add( int x, int y) 25 { 26 edge[eNum].e=y; 27 edge[eNum].next=tail[x]; 28 tail[x]=eNum++; 29 } 30 void Init( int n) 31 { 32 memset(dfn,- 1, sizeof(dfn)); 33 memset(tail,- 1, sizeof(tail)); 34 memset(ins, 0, sizeof(ins)); 35 for( int i= 1;i<=n;i++) 36 { 37 degree[i]= 0; 38 fa[i]=i; 39 } 40 } 41 void Tarjan( int u, int f) 42 { 43 dfn[u]=low[u]=++index; 44 for( int i=tail[u];i!=- 1;i=edge[i].next) 45 { 46 int v=edge[i].e; 47 if(v==f) continue; 48 if(dfn[v]==- 1) 49 { 50 Tarjan(v,u); 51 low[u]=Min(low[u],low[v]); 52 } 53 else 54 low[u]=Min(low[u],dfn[v]); 55 } 56 } 57 58 int main() 59 { 60 int n,m,x,y,num; 61 scanf( " %d%d ",&n,&m); 62 Init(n); 63 index= 0;eNum= 1;s= 0;num= 0; 64 while(m--) 65 { 66 scanf( " %d%d ",&x,&y); 67 Add(x,y); 68 Add(y,x); 69 } 70 for( int i= 1;i<=n;i++) 71 if(dfn[i]==- 1) 72 Tarjan(i,- 1); 73 for( int i= 1;i<=n;i++) 74 { 75 for( int j=tail[i];j!=- 1;j=edge[j].next) 76 { 77 if(low[i]!=low[edge[j].e]) 78 degree[low[i]]++; // 因为是无向图，只记录出度（入度也可） 79 } 80 } 81 for( int i= 1;i<=n;i++) 82 if(degree[i]== 1) 83 num++; 84 for( int i= 1;i<=n;i++) 85 printf( " low[%d]=%d\n ",i,low[i]); 86 printf( " %d\n ",(num+ 1)/ 2); 87 // while(1); 88 return 0;
89 }