1 /*
2 Author: Leo.W
3 Descriptipn: 判断是否为树,即无环联通图。
4 How to Do: 并查集
5 */
6 #include <iostream>
7 #include <string.h>
8 #include <algorithm>
9 using namespace std;
10 #define MAXSIZE 100002
11 int pre[MAXSIZE];
12 bool chose[MAXSIZE];
13 int findSet(int x){
14 if(x!=pre[x])
15 pre[x]=findSet(pre[x]);
16 return pre[x];
17 }
18 void init(){
19 memset(chose,false,sizeof(chose));
20 int i;
21 for(i=0;i<100002;i++)
22 pre[i]=i;
23 }
24 int main(){
25 //freopen("in.txt","r",stdin);
26 int m,n,point,line,flag=1;
27 while (scanf("%d%d",&m,&n)!=EOF){
28 if(m==0){//此处巨坑爹 WA了多次
29 puts("Yes");
30 continue;
31 }
32 if(m==-1&&n==-1)
33 break;
34 init(); point=line=0;
35 do {
36 line++;
37 int a=findSet(m);
38 int b=findSet(n);
39 if(!chose[a]){
40 chose[a]=true; point++;
41 }
42 if(!chose[b]){
43 chose[b]=true; point++;
44 }
45 if(a!=b)
46 pre[a]=b;
47 else
48 flag=0;
49 } while(scanf("%d%d",&m,&n)&&(m&&n));
50 if (flag&&line+1==point)//一定注意图的连通性,第一次就WA了
51 printf("Yes\n");
52 else
53 printf("No\n");
54 }
55 return 0;
56 }
57
posted on 2012-03-15 18:27
Leo.W 阅读(201)
评论(0) 编辑 收藏 引用