ACM___________________________

 

文章作者：yx_th000 文章來源：Cherish_yimi (http://www.cnblogs.com/cherish_yimi/)

l         并查集：(union-find sets)

一種簡單的用途廣泛的集合. 并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，應用很多，如其求無向圖的連通分量個數等。最完美的應用當屬：實現Kruskar算法求最小生成樹。

l         并查集的精髓（即它的三種操作，結合實現代碼模板進行理解）：

1、Make_Set(x) 把每一個元素初始化為一個集合

初始化后每一個元素的父親節點是它本身，每一個元素的祖先節點也是它本身（也可以根據情況而變）。

2、Find_Set(x) 查找一個元素所在的集合

查找一個元素所在的集合，其精髓是找到這個元素所在集合的祖先！這個才是并查集判斷和合并的最終依據。
判斷兩個元素是否屬于同一集合，只要看他們所在集合的祖先是否相同即可。
合并兩個集合，也是使一個集合的祖先成為另一個集合的祖先，具體見示意圖

3、Union(x,y) 合并x,y所在的兩個集合

合并兩個不相交集合操作很簡單：
利用Find_Set找到其中兩個集合的祖先，將一個集合的祖先指向另一個集合的祖先。如圖

l         并查集的優化

1、Find_Set(x)時 路徑壓縮
尋找祖先時我們一般采用遞歸查找，但是當元素很多亦或是整棵樹變為一條鏈時，每次Find_Set(x)都是O(n)的復雜度，有沒有辦法減小這個復雜度呢？
答案是肯定的，這就是路徑壓縮，即當我們經過"遞推"找到祖先節點后，"回溯"的時候順便將它的子孫節點都直接指向祖先，這樣以后再次Find_Set(x)時復雜度就變成O(1)了，如下圖所示；可見，路徑壓縮方便了以后的查找。

2、Union(x,y)時 按秩合并
即合并的時候將元素少的集合合并到元素多的集合中，這樣合并之后樹的高度會相對較小。

l         主要代碼實現

Code
 1 int father[MAX];   /**//* father[x]表示x的父節點*/
 2 int rank[MAX];     /**//* rank[x]表示x的秩*/
 3
 4
 5 /**//* 初始化集合*/
 6 void Make_Set(int x)
 7 {
 8     father[x] = x; //根據實際情況指定的父節點可變化
 9     rank[x] = 0;   //根據實際情況初始化秩也有所變化
10 }
11
12
13 /**//* 查找x元素所在的集合,回溯時壓縮路徑*/
14 int Find_Set(int x)
15 {
16     if (x != father[x])
17      {
18         father[x] = Find_Set(father[x]); //這個回溯時的壓縮路徑是精華
19     }
20     return father[x];
21 }
22
23
24 /**//* 
25    按秩合并x,y所在的集合
26    下面的那個if else結構不是絕對的，具體根據情況變化
27    但是，宗旨是不變的即，按秩合并，實時更新秩。
28 */
29 void Union(int x, int y)
30 {
31     x = Find_Set(x);
32     y = Find_Set(y);
33     if (x == y) return;
34     if (rank[x] > rank[y]) 
35      {
36         father[y] = x;
37     }
38     else
39      {
40         if (rank[x] == rank[y])
41          {
42             rank[y]++;
43         }
44         father[x] = y;
45     }
46 }
47

 

注：學習并查集時非常感謝Slyar提供的資料，這里注明鏈接：http://www.slyar.com/blog/
另外，我認為寫并查集時涉及到的路徑壓縮，最好用遞歸，一方面代碼的可讀性非常好，另一方面，可以更直觀的理解路徑壓縮時在回溯時完成的巧妙。

 

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.

Output

For each case, output the number of suspects in one line.

Sample Input

100 4

2 1 2

5 10 13 11 12 14

2 0 1

2 99 2

200 2

1 5

5 1 2 3 4 5

1 0

0 0

Sample Output

4

1

1

我的思路：

典型的并查集，最初各自為集，然后每個group進行合并，等到所有的group合并完，題目也就解決了，因為在合并的時候，如果哪兩個group中有重合的元素，則那個后來的group會由于按秩合并的原則自動合并到

先有的集合當中，奧妙便在其中。下面是代碼：

Code
 1 #include<iostream>
 2 using namespace std;
 3
 4 int n, m, i, j;
 5 int father[30005], num[30005];
 6
 7 void makeSet(int n)
 8 {
 9     for(i = 0; i < n; i++)
10      {
11         father[i] = i; //使用本身做根
12         num[i] = 1;
13     }
14 }
15 int findSet(int x)
16 {
17     if(father[x] != x) //合并后的樹的根是不變的
18      {    
19         father[x] = findSet(father[x]);
20     }
21     return father[x]; 
22 }
23
24 void Union(int a, int b)
25 {
26     int x = findSet(a);
27     int y = findSet(b);
28     if(x == y)
29      {
30         return;
31     }
32     if(num[x] <= num[y])
33      {
34         father[x] = y;
35         num[y] += num[x];
36     }
37     else 
38      {
39         father[y] = x;
40         num[x] += num[y];
41     }
42 }
43
44 int main()
45 {
46     while(scanf("%d %d", &n, &m)!=EOF && n != 0)
47      {
48         makeSet(n);
49         for(i = 0; i < m; i++)
50          {
51             int count, first, b;
52             scanf("%d %d",&count, &first);
53             for(j = 1; j < count; j++)
54              {
55                 scanf("%d",&b);
56                 Union(first,b);
57             }
58         }
59         printf("%d\n",num[findSet(0)]);
60     }
61     return 0;
62 }
63

另外，上面并查集的根我是采用數字本身的，然后路徑壓縮尋找父親節點是采用遞歸的，下面貼出，采用-1做根和使用非遞歸實現的部分代碼：

Code
 1 void makeSet(int n)
 2 {
 3     for(i = 0; i < n; i++)
 4      {
 5         father[i] = -1;
 6         num[i] = 1;
 7     }
 8 }
 9 //非遞歸實現
10 int findSet(int x)
11 {
12     while(father[x] != -1)   //根為-1
13      {
14         x = father[x];
15     }
16     return x;
17 }
18

 

Ubiquitous Religions

Description

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input

The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

Output

For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

Sample Input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0

Sample Output

Case 1: 1

Case 2: 7

我的思路：

有了前面學習的基礎和1161的練習，這道題完全就可以水過了，設定一個計數器，每次合并時減1便可值得一提的是：樹的秩是好東西啊，既可以記錄每個集合的節點個數，又能保證按秩合并成相對高度小的樹。

代碼如下：

Code
 1 #include<iostream>
 2 using namespace std;
 3
 4 int n, m, maxNum, i;
 5 int father[50005], num[50005];
 6
 7 void makeSet(int n)
 8 {
 9     for(int j = 1; j <= n; j++)
10      {
11         father[j] = j;
12         num[j] = 1;
13     }
14 }
15 int findSet(int x)
16 {
17     if(father[x] != x) 
18      {    
19         father[x] = findSet(father[x]);
20     }
21     return father[x]; 
22 }
23
24 void Union(int a, int b)
25 {
26     int x = findSet(a);
27     int y = findSet(b);
28     if(x == y)
29      {
30         return;
31     }
32     if(num[x] <= num[y])
33      {
34         father[x] = y;
35         num[y] += num[x];
36         maxNum--;
37     }
38     else 
39      {
40         father[y] = x;
41         num[x] += num[y];
42         maxNum--;
43     }
44 }
45
46 int main()
47 {
48     int Case = 1;
49     while(scanf("%d %d", &n, &m)!=EOF && n!=0)
50      {
51         maxNum = n;
52         makeSet(n);
53         int a, b;
54         for(i = 0; i < m; i++)
55          {
56             scanf("%d %d",&a, &b);
57             Union(a,b);
58         }
59         printf("Case %d: %d\n",Case++,maxNum);
60     }
61     return 0;
62 }
63

POJ 1611 The Suspects          最基礎的并查集

 

POJ 2524 Ubiquitous Religions 最基本的并查集

POJ 1182 食物鏈       并查集的拓展

注意: 只有一組數據;

要充分利用題意所給條件:有三類動物A,B,C，這三類動物的食物鏈

構成了有趣的環形。A吃B， B吃C，C吃A。也就是說:只有三個group

POJ 2492 A Bug's Life 并查集的拓展

法一:深度優先遍歷

每次遍歷記錄下該點是男還是女，只有:男-〉女，女-〉男滿足，否則，找到同性戀，結束程序。

法二:二分圖匹配

法三:并查集的拓展:和1182很像，只不過這里就有兩組，而1182是三組,1611無限制

POJ 1861 Network == zju_1542    并查集+自定義排序+貪心求"最小生成樹"

答案不唯一，不過在ZOJ上用QSORT()和SORT()都能過，在POJ上只有SORT()才能過...

POJ 1703 Find them, Catch them 并查集的拓展

這個和POJ 2492 A Bug's Life很像，就是把代碼稍微修改了一下就AC了！

注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是說只有兩個組。

POJ 2236 Wireless Network        并查集的應用

需要注意的地方：1、并查集；2、N的范圍，可以等于1001；3、從N+1行開始，第一個輸入的可以是字符串。

POJ 1988 Cube Stacking            并查集很好的應用

1、與 銀河英雄傳說==NOI2002 Galaxy一樣；2、增加了一個數組behind[x],記錄戰艦x在列中的相對位置；3、詳細解題報告見銀河英雄傳說。

 

JOJ 1905 Freckles   == POJ 2560 最小生成樹

 

法一：Prim算法；法二：并查集實現Kruskar算法求最小生成樹