由“哥尼斯堡的‘七橋問題’”引出的並查集問題
最近做了這麼一個題目：
題目的意思與一筆畫基本一致。給定幾個點個幾條邊，讓你判斷這個點邊構成的無向圖是否可以“一筆畫”。
歐拉回路有這樣一個性質：
若是有向圖，則構成歐拉回路的充要條件是每個點的入度等於出度；
若為無向圖，則構成歐拉回路的充要條件是每個點的度數為偶數。
這個性質仔細一想就能明白，這裡不多做介紹。
這個題麻煩就麻煩在，你並不知道這個圖是不是連通的。所以這個題就不是簡單的去判斷每個點的度數是不是偶數這麼簡單。我們必須先去判斷這個圖是否連通。
問題分析：
這裡只討論連通性的求解。
題目實際上是求圖的連通分支的個數。只要分支個數大於2，這個圖一定不是連通圖。求連通分支一個很簡單的方式是：並查集。
並查集類似於樹的結構。現在我們想：只要拿到了兩個節點，我們都為其連結一個“上級”，連結到最後，讓根節點的上級是它本身，就完成了一個分支的連線。
下面這個圖，每一條就相當於一個分支，每個圓圈就是一個節點。再未完全連線完之前，可能會有很多條這樣的分支，在隨後的連線中，可能會有一對節點將兩條分支連線為一條。到連線結束時，如果有一條分支，則皆大歡喜，要是有兩條以上，那對不起咱們不是連通圖。
所以說，“並查集”，就是同時對多個分支進行搜尋，並在合適的條件下進行合併。查詢與合併也就是並查集的核心。
大概意思就是這樣，下面我們細緻說說這個“並查集”原理到底是如何與怎麼操作。
程式碼分析
並查集主要有一個數組pre[]，陣列角標是當前節點的編號，陣列值是其前驅結點的編號。還有兩個函式find()，join()。
我們建立並查集的第一步是進行初始化。因為上面說過，根節點的判斷標示就是他的前驅節點是它本身，所以我們初始化就讓pre[i]=i，讓每個節點的前驅節點都預設為自己。事實上，這相當於讓每個節點自成一派，等下面連線的時候再認師傅。
1 void init(int num)
2 {
3for (int i = 1; i <= num; i++)//num是你的節點數，編號為了方便從1開始
4{
5pre[i] = i;
6}
7 }
接下來就需要去連線各個分支了。因為我們連線分支時，相連通的只需要一個根節點，所以我們在連線的時候需要將一個分支的根節點放在另一個分支的根節點的後面，也就是讓一個分支的前驅結點是另一個分支的根節點。
1 void join(int x, int y)
2 {
3int t1, t2;
4t1 = find(x);//第一個節點的根節點
5t2 = find(y);//第二個節點的根節點
6if (t1 != t2)//兩個節點如果不是一個節點的話
7pre[t2] = t1;//就讓t2的前驅結點為t1
8//也就是，t2節在了t1後面
9 }
那麼根節點如何尋找呢？
我們可以使用遞迴的思想。只要你的前驅結點不是你本身，我就一直向上尋找，直到前驅等於本身為止。程式碼呼之欲出：
int find(int x)
{
if (x == pre[x])//如果前驅等於本身
return x;//返回，遞迴結束
else
{//不相等：
pre[x] = find(pre[x]);//繼續尋找你的前驅節點，向上尋找。
return pre[x];//返回找到的結果。返回x也一樣，畢竟是相等才停下來的。
}
}
這樣我們這個題基本已經出來了，剩下的就是根據題目修改下我們的判斷條件：
1 int judge(int num)
2 {
3int t = 0;//t用來記錄根節點的數目
4for (int i = 1; i <= num; i++)//遍歷每個節點
5{
6if (pre[i] == i)//如果是根節點
7t++;
8if (du[i] % 2 != 0)//如果度數不是偶數
9return 0;//直接退出，返回假
10}
11if (t != 1)//根節點不是一個的話
12return 0;//就不是連通的了唄
13return 1;//經歷了重重考驗，恭喜你，你是連通的
14 }
完整程式碼：
下面是完整程式碼:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int du[1005];
4 int pre[1004];
5 void init(int num)
6 {
7for (int i = 1; i <= num; i++)
8{
9pre[i] = i;
10}
11 }
12 int find(int x)
13 {
14if (x == pre[x])
15return x;
16else
17{
18pre[x] = find(pre[x]);
19return pre[x];
20}
21 }
22 void join(int x, int y)
23 {
24int t1, t2;
25t1 = find(x);
26t2 = find(y);
27if (t1 != t2)
28pre[t2] = t1;
29 }
30 int judge(int num)
31 {
32int t = 0;
33for (int i = 1; i <= num; i++)
34{
35if (pre[i] == i)
36t++;
37if (du[i] % 2 != 0)
38return 0;
39}
40if (t != 1)
41return 0;
42return 1;
43 }
44 int main()
45 {
46int num, count;
47scanf("%d %d", #, &count);
48init(num);
49int x, y;
50memset(du, 0, sizeof(du));
51
52for (int i = 1; i <= count; i++)
53{
54scanf("%d %d", &x, &y);
55du[x]++;
56du[y]++;
57join(x, y);
58}
59if (judge(num))
60printf("1");
61else
62printf("0");
63
64 }
通過這個小題目，我發現這個連通集是很高效的演算法，很多類似的題目都可以使用這種方式。
最後感謝這個帖子https://blog.csdn.net/u013546077/article/details/64509038