并查集理論基礎

初始化:

void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}

尋根：

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

判斷u跟v是否同根

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

加入并查集：

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

按秩合并的代碼如下：
?

int n = 1005; // n根據題目中節點數量而定，一般比節點數量大一點就好
vector<int> father = vector<int> (n, 0); // C++里的一種數組結構
vector<int> rank = vector<int> (n, 1); // 初始每棵樹的高度都為1// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;rank[i] = 1; // 也可以不寫}
}
// 并查集里尋根的過程
int find(int u) {return u == father[u] ? u : find(father[u]);// 注意這里不做路徑壓縮
}// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 將v->u 這條邊加入并查集
void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (rank[u] <= rank[v]) father[u] = v; // rank小的樹合入到rank大的樹else father[v] = u;if (rank[u] == rank[v] && u != v) rank[v]++; // 如果兩棵樹高度相同，則v的高度+1，因為上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

#include <iostream>
#include <vector>
using namespace std;
int n=101;
vector<int>father(n,0);void init(){for(int i=0;i<n;i++){father[i]=i;}
}int find(int x){if(father[x]==x)return x;else return father[x]=find(father[x]);
}
void join(int u,int v){u=find(u);v=find(v);if(u==v) return;father[v]=u;
}
bool isSame(int u,int v){u=find(u);v=find(v);return u==v;
}int main(){int n,m;cin>>n>>m;init(); // 初始化并查集    上面只是定義 這里要調用for(int i=0;i<m;i++){int s,t;cin>>s>>t;join(s,t);     //這里構建并查集}int source,dest;cin>>source>>dest;bool ans=isSame(source,dest);if(ans)cout<<1;else cout<<0;}