HDU 1272. 输入的逻辑+并查集(判断是否有环)
原题链接
中等
作者:
史一帆
,
2021-05-19 19:00:40
,
所有人可见
,
阅读 210
//flag[i]数组标记i是否出现,FLAG标记是否有环,sum记录集合的个数
#include <iostream>
#include <cstdio>
const int N = 100010;
int flag[N], p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b)
{
int fa = find(a), fb = find(b);
p[fa] = fb;
}
int main()
{
int a, b;
while (~scanf("%d%d",&a,&b))
{
if (a == -1 && b == -1) break;
for (int i = 0; i <= N; i++) flag[i] = 0, p[i] = i;
int FLAG = 0;
while(1)
{
if (a == 0 && b == 0) break;
if (find(a) == find(b)) FLAG = 1; // 在建立两点之间的边时应查询它们的根节点是否相同,如果相同就是有环的,否则无环
merge(a,b);
flag[a] = 1, flag[b] = 1; // 建立完边之后打上标记
scanf("%d%d",&a,&b); // 先对第一次输入的数据判断,所以输入放在最后
}
if (FLAG == 1) printf("No\n");
else
{
int sum = 0;
for (int i = 0; i <= N; i++)
if(flag[i] && p[i] == i)
sum ++ ;
if (sum > 1) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}