首页 > 代码库 > LA 5135 井下矿工（点—双连通分量模板题）
LA 5135 井下矿工（点—双连通分量模板题）
https://vjudge.net/problem/UVALive-5135
题意：
在一个无向图上选择尽量少的点涂黑，使得任意删除一个点后，每个连通分量至少有一个黑点。
思路：
首先dfs遍历求出割顶和双连通分量，并把每个连通分量保存下来。
接下来分情况讨论：
如果一个点—双连通分量只有一个割顶，在该分量中必须将一个非割顶涂黑。
如果一个点—双连通分量有2个及以上的割顶，不需要涂黑。
如果整个图没有割顶，则至少需要涂黑两个点。（因为有可能删除的就是涂黑的点）
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 12 const int maxn=50000+5; 13 int m; 14 15 struct Edge 16 { 17 int u,v; 18 Edge(int x,int y):u(x),v(y){} 19 }; 20 stack<Edge> S; 21 22 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt; 23 vector<int> G[maxn],bcc[maxn]; 24 25 int dfs(int u,int fa) 26 { 27 int lowu=pre[u]=++dfs_clock; 28 int child=0; 29 for(int i=0;i<G[u].size();i++) 30 { 31 int v=G[u][i]; 32 Edge e=Edge(u,v); 33 if(!pre[v]) 34 { 35 S.push(e); 36 child++; 37 int lowv=dfs(v,u); 38 lowu=min(lowu,lowv); 39 if(lowv>=pre[u]) 40 { 41 iscut[u]=true; 42 bcc_cnt++; bcc[bcc_cnt].clear(); 43 for(;;) 44 { 45 Edge x=S.top(); S.pop(); 46 if(bccno[x.u]!=bcc_cnt) {bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;} 47 if(bccno[x.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;} 48 if(x.u==u&&x.v==v) break; 49 } 50 } 51 } 52 else if(pre[v]<pre[u] && v!=fa) 53 { 54 S.push(e); 55 lowu=min(lowu,pre[v]); 56 } 57 } 58 if(fa<0 && child==1) iscut[u]=0; 59 return lowu; 60 } 61 62 void find_bcc(int n) 63 { 64 memset(pre,0,sizeof(pre)); 65 memset(iscut,0,sizeof(iscut)); 66 memset(bccno,0,sizeof(bccno)); 67 dfs_clock=bcc_cnt=0; 68 for(int i=1;i<=n;i++) 69 if(!pre[i]) dfs(1,-1); 70 } 71 72 int main() 73 { 74 //freopen("D:\\input.txt","r",stdin); 75 int kase=0; 76 while(~scanf("%d",&m) && m) 77 { 78 for(int i=1;i<maxn;i++) {G[i].clear();bcc[i].clear();} 79 for(int i=0;i<m;i++) 80 { 81 int u,v; 82 scanf("%d%d",&u,&v); 83 G[u].push_back(v); 84 G[v].push_back(u); 85 } 86 find_bcc(m); 87 long long ans1=0,ans2=1; 88 for(int i=1;i<=bcc_cnt;i++) 89 { 90 int cut_cnt=0; 91 for(int j=0;j<bcc[i].size();j++) 92 { 93 if(iscut[bcc[i][j]]) cut_cnt++; 94 } 95 if(cut_cnt==1) 96 { 97 ans1++; ans2*=(long long)(bcc[i].size()-cut_cnt); 98 } 99 }100 if(bcc_cnt==1)101 {102 ans1=2; ans2=bcc[1].size()*(bcc[1].size()-1)/2;103 }104 printf("Case %d: %lld %lld\n",++kase,ans1,ans2);105 }106 return 0;107 }
LA 5135 井下矿工（点—双连通分量模板题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。