整个文件以两个-1结尾。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 100010
using namespace std;
int per[N], h[N];//数组per用来记录父节点,h数组用来记录出现的点
void init()//对所有点的父节点进行初始化
{
for(int i = 1; i <= N; i++)
per[i] = i;
}
int find(int x)//利用递归寻找某个点的根节点
{
return x==per[x] ? x : find(per[x]);
}
int join(int x, int y)//判断是否成环
{
int fx = find(x);
int fy = find(y);
if(fx == fy)//因为给的两个点本来就是连通的,如果根节点一样,就成环了
return 0;
else
{
per[fx] = fy;
return 1;
}
}
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m), n!=-1 && m!=-1)
{
memset(h, 0, sizeof(h)); //将数组初始化为0,出现的点就标记为1
if(n == 0 && m == 0)
{
printf("Yes\n");
continue;
}
int flag = 1;
h[n] = 1;
h[m] = 1;
init();
join(n, m);
while(~scanf("%d%d", &n, &m), n&&m)
{
int t = join(n, m);//用t记录是否成环
if(!h[n])
h[n] = 1;
if(!h[m])
h[m] = 1;
if(t == 0)如果成环,就令flag = 0
flag = 0;
}
int root = 0;
for(int i = 1; i <= N; i++)//判断根节点的个数
{
if(h[i] && per[i] == i)
root++;
}
if(flag == 0 || root > 1)//根节点的个数大于1或者成环时输出No
printf("No\n");
else
printf("Yes\n");
}
return 0;