題意：給定一無向圖，選擇最少的點，使得刪除任意一個點后，其他的點都與所選擇的點中任意一個聯通

題解：

由于割點上肯定不能放井，所以開始時刪除所有的割點。然后找出所有的雙連通分量，如果雙連通分量上有兩個及以上割點，不用放井；如果只有一個割點，一定要放一個井，然后乘法原理統計答案即可。

至于怎么求雙連通分量，由于一個割點一定是在兩個雙連通分量交界的地方，因此DFS每個未訪問節點，僅當一個點不為割點時擴展該節點。

#include <map> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define ll long longconst int MAXN=500+2; struct HASH{int u;HASH *next;HASH(){}HASH(int _u,HASH *_next):u(_u),next(_next){} }*table[MAXN],mem[2*MAXN]; int N,M,T,f,cnt,ans,t[MAXN],bcc[MAXN]; int dfn[MAXN],low[MAXN],depth; ll s[MAXN],ans_sum; bool flag[MAXN],cut[MAXN]; map<int,int> m;void Insert(int u,int v){table[u]=&(mem[cnt++]=HASH(v,table[u]));table[v]=&(mem[cnt++]=HASH(u,table[v])); }void Tarjan(int f,int x){dfn[x]=low[x]=++depth;int c=0;for(HASH *p=table[x];p;p=p->next)if(!dfn[p->u]){Tarjan(x,p->u),low[x]=min(low[x],low[p->u]),c++;if(low[p->u]>=dfn[x]) cut[x]=1;}else if(p->u!=f && dfn[p->u]<dfn[x]) low[x]=min(low[x],dfn[p->u]);if(!f && c==1) cut[x]=0; }void DFS(int x){flag[x]=1,s[cnt]++;for(HASH *p=table[x];p;p=p->next){if(flag[p->u]) continue;if(!cut[p->u]) DFS(p->u);else if(bcc[p->u]!=cnt) bcc[p->u]=cnt,t[cnt]++;} }int main(){while(scanf("%d",&M)!=EOF && M){N=cnt=ans=depth=0,ans_sum=1,T++;m.clear();memset(t,0,sizeof(t));memset(s,0,sizeof(s));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(cut,0,sizeof(cut));memset(bcc,0,sizeof(bcc));memset(flag,0,sizeof(flag));memset(table,0,sizeof(table));for(int i=1,u,v;i<=M;i++){scanf("%d %d",&u,&v);if(!m[u]) m[u]=++N;if(!m[v]) m[v]=++N;Insert(m[u],m[v]);}for(int i=1;i<=N;i++)if(!dfn[i]) Tarjan(0,i);cnt=0;for(int i=1;i<=N;i++)if(!cut[i] && !flag[i]) ++cnt,DFS(i);if(cnt==1) printf("Case %d: 2 %lld\n",T,N*(N-1)/2);else{for(int i=1;i<=cnt;i++)if(t[i]==1) ans++,ans_sum*=s[i];printf("Case %d: %d %lld\n",T,ans,ans_sum);}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/WDZRMPCBIT/p/6477071.html

總結

以上是生活随笔為你收集整理的BZOJ2730 HNOI2012 矿井搭建 连通性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。