题意:这题和POJ-3177-Redundant Paths差不多..只是这题是一开始是无向图,要求你加几条有向边形成强连通图.即和无向图加几条无向边形成双连通分量是一个意思!
分析:先求双连通分量,然后缩点,形成新图,然后统计点的度数,由于原图可能是不连通的,故可能有孤立的点,即度数为0.
然后统计度数,度数为1的ans加1,度数为0的ans加2,最后(ans+1)/2即是答案.然后注意,若一开始整个图就是一个双连通,则答案为0
// File Name: 10972.cpp // Author: Zlbing // Created Time: 2013/4/30 9:20:22 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=1005; vector<int>G[MAXN],P[MAXN]; int dfs_clock,bcc_cnt; int pre[MAXN]; int first2[MAXN]; int T[MAXN]; int n,m; int dfs1(int u,int fa) { int lowu=pre[u]=++dfs_clock; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!pre[v]) { int lowv=dfs1(v,u); lowu=min(lowu,lowv); if(lowv>pre[u]) { P[v].push_back(u); P[u].push_back(v); } } else if(pre[v]<pre[u]&&v!=fa) { lowu=min(pre[v],lowu); } } return lowu; } void dfs2(int u,int fa) { T[u]=bcc_cnt; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; bool flag=true; for(int j=0;j<P[u].size();j++) { int vv=P[u][j]; if(v==vv) { flag=false;break; } } if(!flag||T[v])continue; dfs2(v,u); } } void find_bcc(int n) { dfs_clock=0,bcc_cnt=0; memset(pre,0,sizeof(pre)); memset(T,0,sizeof(T)); for(int i=1;i<=n;i++) if(!pre[i]) dfs1(i,-1); for(int i=1;i<=n;i++) if(!T[i]) { bcc_cnt++; dfs2(i,-1); } } int degree[MAXN]; int main() { while(~scanf("%d%d",&n,&m)) { REP(i,1,n){ G[i].clear(); P[i].clear(); } REP(i,1,m) { int a,b; scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } CL(degree,0); find_bcc(n); REP(i,1,n) { for(int j=0;j<G[i].size();j++) { int v=G[i][j]; if(T[i]!=T[v]) degree[T[i]]++; } } if(bcc_cnt==1) printf("0\n"); else{ int ans=0; REP(i,1,bcc_cnt) { if(degree[i]==1)ans++; else if(degree[i]==0)ans+=2; } printf("%d\n",(ans+1)/2); } } return 0; }