Redundant Paths
POJ - 3177题意：一个无向图（有重边！！），问至少还要加多少边使得去掉任意一条边后任意两点仍可互达。
和上题poj3352基本相同，不过dfs的时候，不能用v！=f来判断是否能走，而要用当前走的边和上一条边是不是反向边
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int maxv=1010; 7 int n,m; 8 struct Edge{ 9 int v,nex; 10 bool iscut; 11 }e[maxv<<2]; 12 int head[maxv]; 13 int cnt=0; 14 void init(){ 15 memset(head,-1,sizeof(head)); 16 cnt=0; 17 } 18 void add(int u,int v){ 19 e[cnt].iscut=0; 20 e[cnt].v=v; 21 e[cnt].nex=head[u]; 22 head[u]=cnt++; 23 } 24 25 int pre[maxv],d[maxv],bccno[maxv],dfsk,bcc_cnt; 26 bool vis[maxv]; 27 28 int dfs(int u,int id){ 29 int lowu=pre[u]=++dfsk; 30 for(int i=head[u];i!=-1;i=e[i].nex){ 31 int v=e[i].v; 32 if(i==(id^1)) continue;//// 反向边 33 if(!pre[v]){ 34 int lowv=dfs(v,i); 35 lowu=min(lowv,lowu); 36 if(lowv>pre[u]) e[i].iscut=e[i^1].iscut=true; 37 } 38 else lowu=min(lowu,pre[v]); 39 } 40 return lowu; 41 } 42 void dfs1(int u){ 43 vis[u]=1; 44 bccno[u]=bcc_cnt; 45 for(int i=head[u];i!=-1;i=e[i].nex){ 46 if(e[i].iscut) continue; 47 if(!vis[e[i].v]) dfs1(e[i].v); 48 } 49 } 50 void find_bcc(int n){ 51 memset(pre,0,sizeof(pre)); 52 memset(bccno,0,sizeof(bccno)); 53 memset(vis,0,sizeof(vis)); 54 dfsk=bcc_cnt=0; 55 for(int i=0;i<n;i++) if(!pre[i]) dfs(i,-1); 56 for(int i=0;i<n;i++) 57 if(!vis[i]) bcc_cnt++,dfs1(i); 58 } 59 60 int main(){ 61 while(scanf("%d%d",&n,&m)!=EOF){ 62 init(); 63 int u,v; 64 for(int i=0;i<m;i++){ 65 scanf("%d%d",&u,&v); 66 u--;v--; 67 add(u,v); 68 add(v,u); 69 } 70 find_bcc(n); 71 memset(d,0,sizeof(d)); 72 for(int i=0;i<n;i++){ 73 for(int j=head[i];j!=-1;j=e[j].nex){ 74 int v=e[j].v; 75 if(e[j].iscut) d[bccno[v]]++; 76 } 77 } 78 int leaf=0; 79 for(int i=1;i<=bcc_cnt;i++) 80 if(d[i]==1) leaf++; 81 printf("%d ",(leaf+1)/2); 82 } 83 return 0; 84 }