程序员人生 网站导航

HDU3394.Railway――点双连通分量

栏目:php教程时间:2015-05-07 09:06:48

http://acm.hdu.edu.cn/showproblem.php?pid=3394

题目描写:
有1个公园有n个景点,公园的管理员准备修建m条道路,并且安排1些构成回路的参观线路。如果1条道路被多条道路公用,那末这条路是冲突的;如果1条道路没在任何1个回路内,那末这条路是不冲突的

问分别有多少条有冲突的路和没有冲突的路

分析:
刚学点双和边双,看见题目分不清哪一个是哪一个~

这个题目是求点双的。某条边有冲突,说明该点双连通份量中存在两个以上的环,没有冲突说明这条边是桥

怎样判断1个双连通份量中环的个数呢?根据点数跟边数的关系
1.当点数=边数,构成1个环
2.当点数>边数(1条线段,说明这条边是桥)
3.当点数<边数,那末就含1个以上的环了

//296MS 3624K 2190 B #include<cstring> #include<cstdio> #include<iostream> #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,a,b) for(int i=(a);i<(b);++i) #define max(a,b) (a<b?b:a) const int MAXN=10010; const int MAXM=100010; using namespace std; int low[MAXN],dfn[MAXN],Stack[MAXN],bcc[MAXN]; int dfs_clock,top; bool ok[MAXN]; int tmp[MAXN],cc; int n,m; int ans1,ans2; struct Edge{ int to,next; }edge[MAXM<<1];int head[MAXN],tot; void addedge(int u,int v){ edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++; } void init(){ tot=0; memset(head,0xff,sizeof(head)); } void count(){ int sum=0,u,v; for(int i=0;i<cc;++i){ u=tmp[i]; for(int j=head[u];j!=-1;j=edge[j].next){ v=edge[j].to; if(ok[v]) sum++; } } sum/=2; if(sum>cc) ans2+=sum; } void dfs(int u,int pre){ int v; low[u]=dfn[u]=++dfs_clock; Stack[top++]=u; for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(v==pre) continue; if(!dfn[v]){ dfs(v,u); if(low[u]>low[v]) low[u]=low[v]; if(low[v]>dfn[u]) ans1++; if(low[v]>=dfn[u]){ cc=0; memset(ok,false,sizeof(ok)); int vn; for(;;){ vn=Stack[--top]; tmp[cc++]=vn; ok[vn]=true; if(vn==v) break; } tmp[cc++]=u; ok[u]=true; count(); } } else if(low[u]>dfn[v]) low[u]=dfn[v]; } } void solve(){ memset(dfn,0,sizeof(dfn)); dfs_clock=top=0; ans1=ans2=0; for(int i=0;i<n;++i){ if(!dfn[i]) dfs(i,-1); } printf("%d %d ",ans1,ans2); } int main() { #ifndef ONLINE_JUDGE freopen("in.cpp","r",stdin); #endif // ONLINE_JUDGE int u,v; while(scanf("%d%d",&n,&m)==2){ if(n==0&&m==0) break; init(); while(m--){ scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } solve(); } return 0; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐