Tyvj1721(寒假模擬賽提高組) 島嶼 解題報告

  島嶼 

描述 Description

湖面上有n座島嶼，從1~n編號。現在要湖上建橋使得島嶼連接起來。橋雙向通行。

輸入格式 Input Format

輸入第一行有兩個整數n,m。

接下來是m行，按照時間順序每行是一次詢問。每行第一個整數q代表詢問的內容：如果q=1，則接下來是兩個島嶼編號a,b(a≠b)；如果q=2，則接下來是一個島嶼編號c。 

輸出格式 Output Format

對於每個詢問，按次序各輸出一行作爲回答：

q=1時：如果a,b相互可達，則輸出Yes；如果a,b相互不可達，則輸出No，並在a,b之間建一座橋。

q=2時：輸出一個整數x，表示由c出發可以到達的島嶼有x個（不包括c自身）。

樣例輸入 Sample Input

5 9 

1 2 3

1 3 2

2 1

2 2

1 4 5

1 2 4

1 2 5

2 4

2 5

樣例輸出 Sample Output

 No
Yes
0
1
No
No
Yes
3
3

【分析】

還有比這更裸的並查集題目嗎？直接上樹狀並查集，0ms AC無壓力。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25409

01 /*
02 *Problem: Tyvj1721島嶼 (Tyvj 2012寒假模擬賽 提高組 day2-1)
03 *Author: Yee-fan Zhu
04 *Method: Union-Find Sets
05 *GTalk:zyfworks@gmail.com
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 using namespace std;
10 const int MAXN=10001;
11 int N,M;
12 class Node
13 {
14 public:
15     int Pnt;
16     int Num;
17 }UFS[MAXN];
18
19 void UFS_Init(int i)
20 {
21     UFS[i].Num=1;
22     UFS[i].Pnt=i;
23 }
24
25 int UFS_Find(int x)
26 {
27     int i=x;
28     while(i!=UFS[i].Pnt)
29         i=UFS[i].Pnt;
30     int j=x;
31     while(j!=i)
32     {
33         int tmp=UFS[j].Pnt;
34         UFS[j].Pnt=i;
35         j=tmp;
36     }
37     return i;
38 }
39
40 void UFS_Merge(int x, int y)
41 {
42     if(UFS[x].Num>UFS[y].Num)
43     {
44         UFS[y].Pnt=x;
45         UFS[x].Num+=UFS[y].Num;
46     }
47     else
48     {
49         UFS[x].Pnt=y;
50         UFS[y].Num+=UFS[x].Num;
51     }
52 }
53
54 void init()
55 {
56     scanf("%d %d\n",&N,&M);
57     for(int i=1;i<=N;i++)
58         UFS_Init(i);
59    
60     int q,a,b;
61     for(int i=1;i<=M;i++)
62     {
63         scanf("%d",&q);
64         if(q==1)
65         {
66             scanf("%d %d\n",&a,&b);
67             a=UFS_Find(a);
68             b=UFS_Find(b);
69             if(a==b)
70             {
71                 printf("Yes\n");
72                 continue;
73             }
74             printf("No\n");
75             UFS_Merge(a,b);
76             continue;
77         }
78         if(q==2)
79         {
80             scanf("%d\n",&a);
81             a=UFS_Find(a);
82             printf("%d\n",UFS[a].Num-1);
83         }
84     }
85 }
86
87 int main()
88 {
89     //freopen("1721.in","r",stdin);
90     //freopen("1721.out","w",stdout);
91     init();
92     return 0;
93 }