poj3352——Road Construction//最小割边

44424742

题意：最少添加多少条边，可以让图成为双向连通图。
对trajan算法求最小割还没了解透彻，参考博客：http://www.cppblog.com/Icyflame/archive/2009/07/04/89227.html
http://hi.baidu.com/buaa_babt/blog/item/4d9a16c934384e2cf9dc61da.html
http://hi.baidu.com/archersfate/blog/item/c573f07b89faf6e42e73b3a1.html
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,r;#define maxn 1005class node{public:int to,next;};node g[maxn*5];int head[maxn],cnt;int dfn[maxn],low[maxn],du[maxn];void add(int u,int v){g[++cnt].to =v;g[cnt].next =head[u];head[u]=cnt;}void dfs(int u,int fa){dfn[u]=low[u]=++cnt;int i;for(i=head[u];i;i=g[i].next ){int v=g[i].to;if(!dfn[v]){dfs(v,u);low[u]=min(low[u],low[v]);}else if(v!=fa){low[u]=min(low[u],dfn[v]);}}}void solve(){int i,j,ans=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));cnt=0;dfs(1,-1);memset(du,0,sizeof(du));for(i=1;i<=n;i++){for(j=head[i];j;j=g[j].next ){int v=g[j].to;if(low[i]!=low[v]) du[low[i]]++;}}for(i=1;i<=n;i++)if(du[i]==1)ans++;printf("%d\n",(ans+1)/2);}int main(){int a,b;while(scanf("%d%d",&n,&r)!=EOF){cnt=0;while(r--){scanf("%d%d",&a,&b);add(a,b);add(b,a);}solve();}return 0;}