1 //这道题我做了很长时间，主要是概念没搞清，题目题意也不清晰，一系列原因导致做题时间过长。
2 //下面我介绍一下题目思路：
3 //本题主要是并查集的回路判断（根节点是否相同）和以及分支数（判断根节点数）的判断，其他的并查集的基本
4 //例程还是必须的，比如路径压缩。
5 //下面是一段难看的代码，随便看看……，有好看的代码积极上传：）
6
7 #include<iostream>
8 #define N 100100
9 using namespace std;
10
11 int p[N];
12 int ex[N];//设一个数组，记录输入数有多少
13
14 bool isLegal(int x, int y)
15 {
16 int tx,ty;
17 int mx,my;
18 int t;
19
20 tx = x;
21 ty = y;
22
23 while(p[tx])
24 tx = p[tx];
25
26 while(p[ty])
27 ty = p[ty];
28
29 if( tx == ty)
30 return false;
31
32 mx = x;
33 my = y;
34 while(p[mx])
35 {
36 t = p[mx];
37 p[mx] = tx;
38 mx = t;
39 }
40 while(p[my])
41 {
42 t = p[my];
43 p[my] = ty;
44 my = t;
45 }
46 p[tx] = ty;
47 return true;
48 }
49
50 int main()
51 {
52 int x,y;
53 int a,max;//max主要是设置一个界，对树的分支数判断时遍历数组的上界，a是记录第一个是根节点的元素（一个分支一个根节点）
54 bool no = false;
55 memset(p,0,sizeof(p));
56 while(scanf("%d%d",&x,&y)!=EOF)
57 {
58 max = max<x?x:max;
59 max = max<y?y:max;
60 if(x == y && x == -1)
61 exit(0);
62 else if(x== y && x == 0)
63 {
64 if(no)
65 {
66 printf("No\n");
67 no = false;
68 }
69 else
70 {
71 for(int i = 1; i <= max; i++)
72 if(!p[i] && ex[i] == 1)
73 {
74 a = i;
75 break;
76 }
77
78 for(; i <= max; i++)
79 if( (!p[i]) && (i != a) && (ex[i] == 1) )
80 {
81 printf("No\n");
82 no = true;
83 break;
84 }
85 if(!no)
86 printf("Yes\n");
87 }
88 memset(p,0,sizeof(p));
89 memset(ex,0,sizeof(ex));
90 max = -1;
91 no = false;
92
93 }
94 else
95 {
96 ex[x] = 1;
97 ex[y] = 1;
98 if(!isLegal(x,y))
99 no = true;
100 }
101 }
102 return 0;
103 }
104
105 //ASUN……
106