并查集一般在遇到求解冗余關(guān)系，關(guān)系合并，環(huán)的數(shù)量等問題的時(shí)候使用。不需要對各數(shù)值進(jìn)行輸出。

注意與有向無環(huán)圖問題進(jìn)行區(qū)分！

有向無環(huán)圖模板看這里：有向無環(huán)圖講解及模板(C++代碼）_子木呀的博客-CSDN博客_c++ 有向無環(huán)圖

并查集是一個(gè)很優(yōu)美的數(shù)據(jù)結(jié)構(gòu)，很多情況下，提煉問題后，可以用并查集進(jìn)行解決，這里總結(jié)下并查集的模板及注釋，可以直接用

1.并查集的使用：

//初始化并查集 int n = xx.size(); UnionFindSet dsu(n);//初始化并查集//將兩個(gè)點(diǎn)合并 for(int i = 0; i < n; i++){dsu.merge(xx[i], xx[i])//...... }

2.并查集模板(直接用就行，可以根據(jù)需要修改返回值出代碼)?

有兩處優(yōu)化：(1)查詢優(yōu)化 (2)路徑優(yōu)化

//并查集實(shí)現(xiàn) class UnionFindSet{vector<int> F;//并查集容器vector<int> rank;//秩優(yōu)化(如果兩個(gè)都有很多元素的根節(jié)點(diǎn)相遇，將根節(jié)點(diǎn)選為元素較少的那一個(gè)，可以節(jié)省時(shí)間)int n;public://并查集初始化UnionFindSet(int _n){n = _n;F.resize(n);rank.resize(n, 1);for(int i = 0; i < n; i++){F[i] = i;}}//并查集查詢操作int find(int x){return x == F[x] ? x : F[x] = find(F[x]);//查詢優(yōu)化。找到x的根節(jié)點(diǎn)}//并查集合并操作bool merge(int x, int y){int fx = find(x), fy = find(y);if(fx == fy) return false;//兩個(gè)節(jié)點(diǎn)連在同一個(gè)根節(jié)點(diǎn)上則直接返回 不再合并//因?yàn)槭菍⒐?jié)點(diǎn)數(shù)少的連接到節(jié)點(diǎn)數(shù)多的節(jié)點(diǎn)上，當(dāng)fx下面的節(jié)點(diǎn)數(shù)小于fy下面的節(jié)點(diǎn)數(shù)時(shí)，交換fx和fy//即兩個(gè)根節(jié)點(diǎn)相遇時(shí)，將新的根節(jié)點(diǎn)選為節(jié)點(diǎn)數(shù)較多的那一個(gè)，盡量減少find(x)的次數(shù)if(rank[fx] < rank[fy])//合并優(yōu)化swap(fx, fy);F[fy] = fx;//將fy連到fx上(將節(jié)點(diǎn)數(shù)少的連接到節(jié)點(diǎn)數(shù)多的上面)rank[fx] += rank[fy];//將fy連到fx后 fx下面的節(jié)點(diǎn)數(shù)目要更新return true;} };

結(jié)合輸入的方式，不使用類。完全可以用的一個(gè)示例：

#include <iostream> #include<vector> #include<string> #include <unordered_map> #include <unordered_set> #include <queue> #include <algorithm>//算法頭文件 #include <numeric> #include <stack> #include<typeinfo> using namespace std;vector<int> F; // 初始化 void UnionFindSet(int N) {F.resize(N + 1, -1);//如果初始化是從1開始，這里就得用N+1 如果從0開始初始化 就用N（從多少開始初始化 根據(jù)輸入的數(shù)據(jù)進(jìn)行調(diào)整）for (int i = 1; i <= N; i++){F[i] = i; // 初始化時(shí)， 將自己初始化為自己的領(lǐng)導(dǎo)} }// 查找 int find(int n) {return n == F[n] ? n : find(F[n]); }// 合并 這里直接在主程序里調(diào)用了查找 能夠省去調(diào)用合并函數(shù)的次數(shù) void merge(int leaderX, int leaderY) {if (leaderX < leaderY){F[leaderX] = leaderY;}else{F[leaderY] = leaderX;} }// 輸入數(shù)組, 每一行表示一個(gè)集合關(guān)系， 比如第一行表示3和4屬于一個(gè)集合 int input[] = {1, 4,2, 5,3, 6,4, 2,5, 1,6, 3, };int main() {int N;cin >> N;int numberOfSets = N;// 初始化領(lǐng)導(dǎo)UnionFindSet(N);int n = sizeof(input) / sizeof(input[0]) / 2;//這地方根據(jù)輸入的形式調(diào)整int j = 0;for (int i = 0; i < n; i++){int u = input[j++];int v = input[j++];u = find(u);//這里直接在主程序里調(diào)用了查找 能夠省去調(diào)用合并函數(shù)的次數(shù)v = find(v);if (u != v) { //如果沒關(guān)系 就合并 最后numberOfSets就是不能合并的個(gè)數(shù) 也就是有幾個(gè)圈子merge(u, v);numberOfSets--;}}cout << numberOfSets << endl;return 0; }

統(tǒng)計(jì)某個(gè)節(jié)點(diǎn)下掛了多少個(gè)節(jié)點(diǎn)

#include <iostream> #include<vector> #include<string> #include <unordered_map> #include <unordered_set> #include <queue> #include <algorithm>//算法頭文件 #include <numeric> #include <stack> #include<typeinfo> using namespace std; vector<int> F; // 初始化 void UnionFindSet(int N) {F.resize(N + 1, -1);//如果初始化是從1開始，這里就得用N+1 如果從0開始初始化 就用N（從多少開始初始化 根據(jù)輸入的數(shù)據(jù)進(jìn)行調(diào)整）for (int i = 1; i <= N; i++){F[i] = i; // 初始化時(shí)， 將自己初始化為自己的領(lǐng)導(dǎo)} }// 查找 int find(int n) {return n == F[n] ? n : find(F[n]); }int main() {int N, M;cin >> N >> M;vector<vector<int>> input;vector<int> intput1;int a,b;for (int i = 0; i < M; i++) {cin >> a >> b;intput1.push_back(a);intput1.push_back(b);input.push_back(intput1);}// 初始化領(lǐng)導(dǎo)UnionFindSet(N);for (int i = 0; i < M; i++){int u = input[i][0];int v = input[i][1];u = find(u);//這里直接在主程序里調(diào)用了查找 能夠省去調(diào)用合并函數(shù)的次數(shù)v = find(v);if (u != v) { //如果沒關(guān)系 就合并 最后numberOfSets就是不能合并的個(gè)數(shù) 也就是有幾個(gè)圈子F[v] = u;}}int numberOfSets = 0;for (int i = 0; i < F.size(); i++) {if (F[i] == 1)numberOfSets++;}cout << numberOfSets+1 << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的C++ 并查集模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。