2789=小鑫的城堡

 1 #include <stdio.h>
 2 #include <string.h>
 3 int merge[100000],keep[100000];//merge数组用来寻找记录最终节点的数组，keep用来记录是否存在某个点。
 4 int root(int x)//用来寻找最终节点。
 5 {
 6     while(x!=merge[x])
 7          x=merge[x];//不断地循环，知道找到最终节点。
 8     return x;
 9 }
10 void find(int a, int b)
11 {
12     if(root(a)!=root(b))
13         merge[root(a)]=root(b);//如果最终节点不同，讲b所带的节点视为最终节点。
14 }
15 int main()
16 {
17     int n;
18     int i,a,b;
19     while(~scanf("%d",&n))
20     {//t的作用是记录点是否达到n+1个，因为不存在回路，即可以视为除了随机一个点之外每个点都可以发出一条路线。
21         int t=0,z=1;//z是用来记录，是否有回路，即29行输入的两点是否存在相同的最终节点，判断在40-43行。
22         memset(keep,0,sizeof(keep));//0为不存在，1为存在，具体参考30-39行代码。
23         for(i=1; i<=100000; i++)
24         {
25             merge[i]=i;//所有的点的最终节点都视为它们本身。
26         }
27         for(i=0; i<n; i++)
28         {
29             scanf("%d %d",&a,&b);
30             if(keep[a]==0)
31             {
32                 keep[a]=1;
33                 t++;
34             }
35             if(keep[b]==0)
36             {
37                 keep[b]=1;
38                 t++;
39             }
40             if(root(a)==root(b))
41             {
42                 z=0;
43             }
44             else
45             {
46                 t--;
47             }
48             find(a,b);
49         }
50         if(z==1&&t==1)printf("Yes
");
51         else printf("No
");//注意大小写，绊在这十分钟=.=。
52     }
53 }