题解 UVA1108 【Mining Your Own Business】

swiftc

2020-02-24 20:12:14

Solution

首先```tarjan```求割点和边双联通分量,然后对于每一个边双联通分量: - 若没有割点 需要建两个出口,在任意两个位置即可。 - 若有一个割点 需要建一个出口,不在割点即可。 - 若有两个以上的割点 无需建出口。 __code__: ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int head[100001],nxt[100001],to[100001],cnt,cas; void add(int a,int b){ nxt[++cnt]=head[a]; to[cnt]=b; head[a]=cnt; } int T,dfn[100001],low[100001],is[100001],vis[100001]; void tarjan(int now,int f){ int flag=0,num=0; low[now]=dfn[now]=++T; for(int i=head[now];i;i=nxt[i]){ if(!dfn[to[i]]){ tarjan(to[i],now); low[now]=min(low[now],low[to[i]]); if(low[to[i]]>=dfn[now]){ flag=1; num++; } } else if(to[i]!=f){ low[now]=min(low[now],dfn[to[i]]); } } if((now==f&&num>=2)||(now!=f&&flag)){ is[now]=1; } } int num1,num2,bel; void dfs(int now){ vis[now]=bel; num1++; for(int i=head[now];i;i=nxt[i]){ if(is[to[i]]&&vis[to[i]]!=bel){ vis[to[i]]=bel; num2++; } if(!vis[to[i]]){ dfs(to[i]); } } } void clear(){ memset(is,0,sizeof(is)); memset(dfn,0,sizeof(dfn)); cnt=0; bel=0; memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); } signed main(){ int n,m; while(scanf("%lld",&m)!=EOF){ if(!m)break; clear(); n=0; for(int i=1;i<=m;i++){ int a,b; scanf("%lld%lld",&a,&b); add(a,b); add(b,a); n=max(n,max(a,b)); } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i,i); } } int ans1=0,ans2=1; for(int i=1;i<=n;i++){ if(vis[i]==0&&is[i]==0){ bel++; num1=num2=0; dfs(i); if(num2==0){ ans1+=2; ans2*=(num1-1)*num1/2; } if(num2==1){ ans1++; ans2*=num1; } } } printf("Case %lld: %lld %lld\n",++cas,ans1,ans2); } return 0; } ```