首页 > 代码库 > poj 3177 求至少添加多少条边可以成为边-双连通图（有重边）

poj 3177 求至少添加多少条边可以成为边-双连通图（有重边）

2024-07-14 14:02:39   214人阅读

【题意】：给出一张无向连通图，求添加多少条边可以成为边-双连通图

【思路】：同3352 一样，求出边-双连通分量，缩点就成了一棵树，求这棵树里的出度为1 的点num  结果是(num-1)/2;

               但是！！  这里和3352 哟一点不一样就是这里有重边，当有重边的时候，不同low值的两点可能属于同一个边-双连通分量

               所以在构图的时候要注意把重边去掉！

  1 #include<iostream>  2 #include<stdio.h>  3 #include<string.h>  4 #include<stack>  5 #include<vector>  6 using namespace std;  7   8 int pre[1002],low[1002],n,adj[1002],num,c,du[1002],count1[5005];  9  10  11 struct E 12 { 13     int to; 14     int next; 15 } edge[500000]; 16  17  18 stack <int>s; 19  20 void add(int a,int b) 21 { 22     count1[a]++; 23     edge[num].to=b; 24     edge[num].next=adj[a]; 25     adj[a]=num++; 26 } 27  28 int dfs(int u,int fa) 29 { 30     int i,v,lowv; 31     pre[u]=low[u]=c++; 32     for(i=adj[u]; i!=-1; i=edge[i].next) 33     { 34         int v; 35         v=edge[i].to; 36         if(v!=fa&&pre[v]<pre[u]) 37         { 38             if(!pre[v]) 39             { 40                 lowv=dfs(v,u); 41                 low[u]=min(low[u],lowv); 42             } 43             else if(pre[v]&&v!=fa) 44                 low[u]=min(low[u],pre[v]); 45         } 46     } 47     return low[u]; 48 } 49  50 int main() 51 { 52     int a,b,m,i,v; 53     while(~scanf("%d%d",&n,&m)) 54     { 55         //printf("fddfd"); 56         memset(adj,-1,sizeof(adj)); 57         memset(count1,0,sizeof(count1)); 58         num=0; 59         while(m--) 60         { 61             scanf("%d%d",&a,&b); 62             for(i=adj[a];i!=-1;i=edge[i].next) 63                 if(edge[i].to==b) 64                     break; 65             if(i==-1||count1[a]==0)    //判断是否是重边 是就不要添加了 66             { 67                 //printf("11 okok  \n"); 68                 add(a,b); 69             } 70  71             for(i=adj[b];i!=-1;i=edge[i].next) 72                 if(edge[i].to==a) 73                     break; 74             if(i==-1||count1[b]==0) 75             { 76                 //printf("22 okok  \n"); 77                 add(b,a); 78             } 79  80         } 81         c=1; 82  83         memset(pre,0,sizeof(pre)); 84         for(int i=1; i<=n; i++) 85             if(pre[i]==0) 86                 dfs(i,-1); 87  88         memset(du,0,sizeof(du)); 89  90  91  92         for(int u=1; u<=n; u++) 93         { 94             for(i=adj[u]; i!=-1; i=edge[i].next) 95             { 96                 int v; 97                 v=edge[i].to; 98                 if(low[u]!=low[v]) 99                 {100                     du[low[u]]++;101                     du[low[v]]++;102                 }103             }104             // printf("%d  %d\n",u,low[u]);105         }106         int ans=0;107         for(int i=0; i<=n; i++)108             if(du[i]/2==1)109                 ans++;110 111         printf("%d\n",(ans+1)/2);112 113     }114     return 0;115 }

 


联系
我们