首页 > 代码库 > BZOJ 1116 [POI2008]CLO（并查集）
BZOJ 1116 [POI2008]CLO（并查集）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1116
【题目大意】
Byteotia城市有n个towns，m条双向roads.每条road连接两个不同的towns,
没有重复的road.你要把其中一些road变成单向边使得：每个town都有且只有一个入度
【题解】
我们发现当一个连通块边数大于等于其点数的时候就满足条件，
那么此题如果出现边数少于点数的连通块就不成立，
用并查集能够完成判断。
【代码】
#include <cstdio>#include <cstring>using namespace std;const int N=100010;int f[N],n,m,mark[N];int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++)f[i]=i,mark[i]=0; while(m--){ int u,v; scanf("%d%d",&u,&v); if(sf(u)==sf(v)){ f[sf(u)]=sf(v); mark[sf(v)]=1; }else{ if(mark[sf(v)])f[sf(u)]=sf(v); else f[sf(v)]=sf(u); } }int flag=1; for(int i=1;i<=n;i++){ if(sf(i)==i&&!mark[i]){flag=0;break;} }puts(flag?"TAK":"NIE"); }return 0;}BZOJ 1116 [POI2008]CLO（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。