并查集理論基礎

背景

當我們需要判斷兩個元素是否在同一個集合里的時候，我們就要想到用并查集。

并查集主要有兩個功能：

• 將兩個元素添加到一個集合中。
• 判斷兩個元素在不在同一個集合

原理講解

?從代碼層面，我們如何將兩個元素添加到同一個集合中呢。

只需要用一個一維數組來表示，即：father[A] = B，father[B] = C 這樣就表述 A 與 B 與 C連通了（有向連通圖）。

// 將v，u 這條邊加入并查集
void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (u == v) return; // 如果發現根相同，則說明在一個集合，不用兩個節點相連直接返回father[v] = u;
}

我們的目的是判斷這三個元素是否在同一個集合里，知道 A 連通 B 就已經足夠了。

這里要講到尋根思路，只要 A ，B，C 在同一個根下就是同一個集合。

給出A元素，就可以通過 father[A] = B，father[B] = C，找到根為 C。

給出B元素，就可以通過 father[B] = C，找到根也為為 C，說明 A 和 B 是在同一個集合里。

// 并查集里尋根的過程
int find(int u) {if (u == father[u]) return u; // 如果根就是自己，直接返回else return find(father[u]); // 如果根不是自己，就根據數組下標一層一層向下找
}

我們需要 father[C] = C，即C的根也為C，這樣就方便表示 A，B，C 都在同一個集合里了。

所以father數組初始化的時候要 father[i] = i，默認自己指向自己。

// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}

最后我們如何判斷兩個元素是否在同一個集合里，如果通過 find函數 找到 兩個元素屬于同一個根的話，那么這兩個元素就是同一個集合，

// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}

?路徑壓縮

在實現 find 函數的過程中，我們知道，通過遞歸的方式，不斷獲取father數組下標對應的數值，最終找到這個集合的根。

如果這棵多叉樹高度很深的話，每次find函數 去尋找根的過程就要遞歸很多次。

我們的目的只需要知道這些節點在同一個根下就可以，所以對這棵多叉樹的構造只需要這樣就可以了，除了根節點其他所有節點都掛載根節點下，這樣我們在尋根的時候就很快，只需要一步，如果我們想達到這樣的效果，就需要?路徑壓縮，將非根節點的所有節點直接指向根節點。

我們只需要在遞歸的過程中，讓 father[u] 接住 遞歸函數 find(father[u]) 的返回結果。

因為 find 函數向上尋找根節點，father[u] 表述 u 的父節點，那么讓 father[u] 直接獲取 find函數 返回的根節點，這樣就讓節點 u 的父節點 變成根節點。

// 并查集里尋根的過程
int find(int u) {if (u == father[u]) return u;else return father[u] = find(father[u]); // 路徑壓縮
}

并查集主要有三個功能。

1. 尋找根節點，函數：find(int u)，也就是判斷這個節點的祖先節點是哪個
2. 將兩個節點接入到同一個集合，函數：join(int u, int v)，將兩個節點連在同一個根節點上
3. 判斷兩個節點是否在同一個集合，函數：isSame(int u, int v)，就是判斷兩個節點是不是同一個根節點

107. 尋找存在的路徑

107. 尋找存在的路徑

題目描述

給定一個包含 n 個節點的無向圖中，節點編號從 1 到 n （含 1 和 n ）。

你的任務是判斷是否有一條從節點 source 出發到節點 destination 的路徑存在。

輸入描述

第一行包含兩個正整數 N 和 M，N 代表節點的個數，M 代表邊的個數。

后續 M 行，每行兩個正整數 s 和 t，代表從節點 s 與節點 t 之間有一條邊。

最后一行包含兩個正整數，代表起始節點 source 和目標節點 destination。

輸出描述

輸出一個整數，代表是否存在從節點 source 到節點 destination 的路徑。如果存在，輸出 1；否則，輸出 0。

輸入示例

5 4
1 2
1 3
2 4
3 4
1 4

輸出示例

1

#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father=vector<int>(101,0);
void init(){for(int i=1;i<=n;i++){father[i]=i;}
}
int find(int u){return u==father[u]?u:father[u]=find(father[u]);
}
bool isSame(int u,int v){u=find(u);v=find(v);return u==v;
}
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}int main(){int m,s,t,ss,d;cin>>n>>m;init();while(m--){cin>>s>>t;join(s,t);}cin>>ss>>d;if(isSame(ss,d))cout<<1<<endl;else cout<<0<<endl;
}