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 阅读(125) 评论(0)  编辑 收藏 引用