B - 小希的迷宫

Sample Input

6 8 5 3 5 2 6 4
5 6 0 0

8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0

3 8 6 8 6 4
5 3 5 6 5 2 0 0

-1 -1

Sample Output

Yes
Yes
No

这道题除了基本的判断跟结点的数量是否为1，还要在每次路径输入的时候判断两房间是否已经连通（即两房间的根节点是否相同），如果相同用一个标记变量来记录。
还要进行特判当一组的输入仅有0 0时，表示没有房间，此时也成立。

#include<stdio.h>
#include<string.h>

int bcj[100005];
bool mark[100005];
int Find(int x)
{
    if(bcj[x] < 0) return x;
    return bcj[x] = Find(bcj[x]);
}

void Union(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x == y) return ;
    bcj[x] += bcj[y];
    bcj[y] = x;
}

int main()
{
	int x,y;
	bool flag;
	while(scanf("%d%d",&x,&y)!=EOF)
	{
		flag=0;
		if(x==-1&&y==-1) break;
		if(x==0&&y==0)
		{
			printf("Yes\n");//特判 
			continue;	
		} 
		memset(bcj,-1,sizeof bcj);
		memset(mark,0,sizeof mark);
		Union(x,y);
		mark[x]=mark[y]=1;
		while(true)
		{
			scanf("%d%d",&x,&y);
			if(x==0&&y==0) break;
			if(Find(x)==Find(y))
			{
				flag=1;
			}
			Union(x,y);
			mark[x]=mark[y]=1;
		}
		int cnt=0;
		for(int i=1;i<=100000;i++)
		{
			if(mark[i]&&bcj[i]<0) cnt++;
		}
		if(flag) printf("No\n");
		else if(cnt==1) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}