首页 > 代码库 > UVAlive5135_Mining Your Own Business
UVAlive5135_Mining Your Own Business
好题。给一个无向图，求最少染黑多少个点后，使得任意删除一个点，每一个点都有与至少一个黑点联通。
一开始的确不知道做。看白书，对于一个联通分量，如果它有两个或以上的割点，那么这个分量中间的任何一个点都是不需要染色的。如果这个联通分量恰好有一个割点，那么这个分量需要对其中任何一个非割点染色，如果分量没有割点，那么任意取两个染色即可。
理解也不难，因为最多只是删除一个点，所以假如删除的不是割点，分量里面是绝对联通的，同时还可以通过割点对外面进行联通，如果删除的是割点，那么外面的与里面的不联通，那么这时就需要里面至少有一个黑点了。如果有两个割点，显然，无论你去掉哪一个点，这个分量都是与外面联通的。
有了这个思路题目就简单了。
召唤代码君：
解法一：找出所有的联通分量，判断每一个连通分量的割点数，更新答案。
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#define maxn 201000typedef long long ll;using namespace std;int first[maxn],next[maxn],to[maxn],edge;//graphvector<int> bcc[maxn];int N,bccnum;//the bcc dataint iscut[maxn],belong[maxn],d[maxn],low[maxn],child;int U[maxn],V[maxn],stack[maxn],top;//stackint n,m,cas=0,T;ll ans,tot;void _init(){ ans=1,tot=0,edge=-1,child=bccnum=0,top=0; for (int i=1; i<=n; i++) first[i]=-1,d[i]=low[i]=iscut[i]=belong[i]=0;}void addedge(int uu,int vv){ edge++; to[edge]=vv,next[edge]=first[uu],first[uu]=edge; edge++; to[edge]=uu,next[edge]=first[vv],first[vv]=edge;}void dfs(int cur,int fa){ d[cur]=low[cur]=d[fa]+1; for (int i=first[cur]; i!=-1; i=next[i]) { if (to[i]==fa) continue; if (!d[to[i]]) { if (fa==0) child++; top++; U[top]=cur,V[top]=to[i]; dfs(to[i],cur); low[cur]=min(low[cur],low[to[i]]); if (low[to[i]]>=d[cur]) { iscut[cur]=1; bccnum++,bcc[bccnum].clear(); for (;;top--) { if (belong[U[top]]!=bccnum) belong[U[top]]=bccnum,bcc[bccnum].push_back(U[top]); if (belong[V[top]]!=bccnum) belong[V[top]]=bccnum,bcc[bccnum].push_back(V[top]); if (U[top]==cur && V[top]==to[i]) { top--; break; } } } } else low[cur]=min(low[cur],d[to[i]]); } if (fa==0 && child==1) iscut[cur]=0;}int main(){ while (scanf("%d",&m) && (m)) { n=-1; for (int i=1; i<=m; i++) { scanf("%d%d",&U[i],&V[i]); n=max(n,max(U[i],V[i])); } _init(); for (int i=1; i<=m; i++) addedge(U[i],V[i]); for (int i=1; i<=n; i++) if (!d[i]) { if (first[i]==-1) { tot++; continue; } child=0; dfs(i,0); } for (int i=1; i<=bccnum; i++) { int cutnum=0; for (unsigned j=0; j<bcc[i].size(); j++) if (iscut[bcc[i][j]]) cutnum++; if (cutnum==1) { tot++; ans*=bcc[i].size()-1; } else if (cutnum==0) { tot+=2; ll tmp=bcc[i].size(); ans*=tmp*(tmp-1)/2; } } printf("Case %d: %lld %lld\n",++cas,tot,ans); } return 0;
解法二：标记所有割点，每次从非割点出发，看能走到多少非割点，而且总共与多少割点相邻，（其实也就是遍历了一遍联通分量，不过实现简单一些）。
#include <iostream>#include <cstdio>#include <cstring>#define maxn 200200typedef long long ll;using namespace std;int first[maxn],to[maxn],next[maxn],edge;int U[maxn],V[maxn];int d[maxn],low[maxn],tag[maxn];bool iscut[maxn],vis[maxn];int n,m,tot,child,sum,cut;ll ans;void _init(){ tot=0,ans=1,edge=-1; for (int i=1; i<=n; i++) first[i]=-1,iscut[i]=vis[i]=false,tag[i]=low[i]=d[i]=0;}void addedge(int uu,int vv){ edge++; to[edge]=vv,next[edge]=first[uu],first[uu]=edge; edge++; to[edge]=uu,next[edge]=first[vv],first[vv]=edge;}void dfs(int cur,int fa){ d[cur]=low[cur]=d[fa]+1; for (int i=first[cur]; i!=-1; i=next[i]) { if (to[i]==fa) continue; if (!d[to[i]]) { if (fa==0) child++; dfs(to[i],cur); low[cur]=min(low[cur],low[to[i]]); if (low[to[i]]>=d[cur]) iscut[cur]=true; } else low[cur]=min(low[cur],d[to[i]]); } if (fa==0 && child==1) iscut[cur]=false;}void visit(int cur,int TAG){ sum++,vis[cur]=true; for (int i=first[cur]; i!=-1; i=next[i]) { if (iscut[to[i]] && tag[to[i]]!=TAG) cut++,tag[to[i]]=TAG; else if (!iscut[to[i]] && !vis[to[i]]) visit(to[i],TAG); }}int main(){ int cas=0; while (scanf("%d",&m) && (m)) { n=0; for (int i=1; i<=m; i++) scanf("%d%d",&U[i],&V[i]),n=max(n,max(U[i],V[i])); _init(); for (int i=1; i<=m; i++) addedge(U[i],V[i]); for (int i=1; i<=n; i++) if (!d[i]) { child=0; dfs(i,0); } for (int i=1; i<=n; i++) if (!vis[i] && !iscut[i]) { cut=sum=0; visit(i,i); if (cut==0) tot+=2,ans*=(ll)sum*(sum-1)/2; else if (cut==1) tot++,ans*=sum; } printf("Case %d: %d %lld\n",++cas,tot,ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。