首页 > 代码库 > POJ 3177

POJ 3177

2024-07-16 20:04:09   212人阅读

这题要的是我们求出我们需要增加多少条边才能让整个图变成一整个双连通块。

可以进行对图缩点。

缩点后，新图是一棵树，树的边就是原无向图的桥。

现在问题转化为：在树中至少添加多少条边能使图变为双连通图。

结论：添加边数=（树中度为1的节点数+1）/2

 1 include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 using namespace std; 5 const int N=10002; 6 int dfn[N],low[N],first[N],in[N]; 7 bool visit[N]; 8 int mun,deep,sum,n; 9 struct edge{10     int v,next;11 }e[N];12 void init(){13     mun=0;14     deep=0;15     sum=0;16     memset(first,-1,sizeof(first));17     memset(dfn,0,sizeof(dfn));18     memset(low,0,sizeof(low));19     memset(in,0,sizeof(in));20 }21 void addedge(int u,int v){22     e[mun].v=v;23     e[mun].next=first[u];24     first[u]=mun++;25 }26 void dfs(int u,int fa){27     dfn[u]=low[u]=++deep;28     for(int i=first[u];i!=-1;i=e[i].next){29         int v=e[i].v;30         if(!dfn[v]){31             dfs(v,u);32             low[u]=min(low[v],low[u]);33         }34         else if(v!=fa)low[u]=min(low[u],dfn[v]);35     }36 }37 void count(){38     for(int i = 1;i <=n;i ++){39         memset(visit,0,sizeof(visit));                                  //visit是为了防止重边40         for(int j=first[i];j!=-1;j=e[j].next){41             int v=e[j].v;42             if (low[v]!= low[i]&&!visit[v]){in[low[i]]++;visit[v]=1;}43         }44     }45     for (int i = 1;i <= n;i ++)                                         //统计度为1的边数46         if (in[i] == 1) sum ++;47 }48 int main(){49     int x,y,m;50     while(scanf("%d%d",&n,&m)!=EOF){51         init();52         while(m--){53             scanf("%d%d",&x,&y);                                        //边为双向；54             addedge(x,y);55             addedge(y,x);56         }57         dfs(1,-1);58         count();59         printf ("%d\n",(sum + 1)/2);60     }61     return 0;62 }

 


联系
我们