数据结构--并查集-高效处理连通性问题

目录

一、理论基础

（1）并查集的功能及实现原理

 （2）代码模版

（3）模拟过程

（4）应用

二、基础题练习

（1）寻找存在的路径（模版题）

（2）排座位

 （3）部落

（4）红色警报

 （5）冗余连接

---

一、理论基础

（1）并查集的功能及实现原理

首先要知道并查集可以解决什么问题呢？

当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

• 将两个元素添加到一个集合中。
• 判断两个元素在不在同一个集合

 如何将两个元素添加到一个集合中？

        将三个元素A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢。

        只需要用一个一维数组来表示，即：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;
}

        find函数是如何实现的呢？其实就是通过数组下标找到数组元素，一层一层寻根过程，代码如下：

// 并查集里寻根的过程
int find(int u) {if (u == father[u]) return u; // 如果根就是自己，直接返回else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

路径压缩：

// 并查集里寻根的过程
int find(int u) {if (u == father[u]) return u;else return father[u] = find(father[u]); // 路径压缩
}

默认自己指向自己，所以

// 并查集初始化
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;
}

 （2）代码模版

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {if (u == father[u]) return u;else return father[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 (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。

1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

（3）模拟过程

join(3, 8) 在图中为什么 将 元素1 连向元素 3 而不是将 元素 8 连向 元素 3 呢？

        因为在join(int u, int v)函数里 要分别对 u 和 v 寻根之后再进行关联。

 

  为什么 图中 8 又直接指向了 3 了呢？

        代码在寻找根的过程中，会有路径压缩的优化        ，减少 下次查询的路径长度。

 

这里为什么是 2 指向了 6，因为 9的根为 2，所以用2指向6。

（4）应用

连通性问题（图论）：判断两点是否在同一个连通块、连通块计数

        【把图中每条边两端的点用并查集合并，判断某两个点是否在同一个集合里，就等于判断它们是否在同一个连通块中。查询连通性：判断两个点 a 和 b 是否连通，只需看 find(a) == find(b) 是否成立。】

        【遍历所有节点，统计父节点为自身的节点数量（即根节点数量），即为连通块个数。if (fa[s] == s) landcount++;】

最小生成树 

二、基础题练习

（1）寻找存在的路径（模版题）

      

 并查集基础题目，题目中各个点是双向图链接，那么判断 一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。

此时我们就可以直接套用并查集模板。

        使用 join(int u, int v)将每条边加入到并查集-----> isSame(int u, int v) 判断是否是同一个根 就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int father[N];
int n; // 节点数量// 并查集里寻根的过程
int find(int x) {if( x==father[x]) return x;else return father[x]=find(father[x]);
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void merge(int u, int v) {int uu = find(u); // 寻找u的根int vv = find(v); // 寻找v的根if (uu == vv) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[vv] = uu;
}int main() {int m, s, t, source, destination;cin >> n >> m;//初始化并查集for (int i = 1; i <= n; i++)  father[i] = i;//合并集合while (m--) {cin >> s >> t;merge(s, t);}//查询是够在一个集合cin >> source >> destination;//判断if (isSame(source, destination)) cout << 1 << endl;else cout << 0 << endl;
}

 

（2）排座位

#include <bits/stdc++.h> 
using namespace std;const int N = 110;       // 最大节点数
int fa[N], g[N][N];      // fa数组表示并查集的父节点，g是邻接矩阵记录关系（朋友或敌人）// 并查集的查找函数，带路径压缩
int find(int x) {if (x == fa[x]) return x;           // 如果当前节点是自己的根，返回它自己else return fa[x] = find(fa[x]);    // 否则递归查找，并路径压缩
}// 并查集的合并函数
void merge(int x, int y) {int xx = find(x);   // 找到x的根int yy = find(y);   // 找到y的根if (xx == yy) return; // 如果已经在同一个集合中，不用合并fa[yy] = xx;          // 否则把y的集合合并到x中return;
}int main() {int n, m, k;cin >> n >> m >> k;  // n个点，m条关系，k次查询// 初始化并查集：每个点的父亲是自己for (int i = 1; i < N; i++) fa[i] = i;// 输入m条关系for (int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z;g[x][y] = g[y][x] = z; // 建图，g[x][y] = z，z是关系类型（1表示朋友，-1表示敌人）if (z == 1)            // 如果是朋友merge(x, y);      // 用并查集把他们合并为一个集合}// k 次查询while (k--) {int x, y;cin >> x >> y;int xx = find(x), yy = find(y); // 找到两个点所在的集合根if (xx == yy && g[x][y] != -1)       // 如果在一个集合，并且不是敌人cout << "No problem" << endl;else if (xx != yy && g[x][y] != -1)  // 如果不在一个集合，但不是敌人（可能认识但不熟）cout << "OK" << endl;else if (xx == yy && g[x][y] == -1)  // 如果在一个集合但是敌人（朋友里有矛盾）cout << "OK but..." << endl;else                                 // 不在一个集合，又是敌人（八竿子打不着）cout << "No way" << endl;}
}

 （3）部落

 

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10; // 最大编号范围，保证能容纳所有人
int fa[N];              // 并查集的父亲数组
map<int, bool> st;      // 用于记录输入中出现过的人（防止0~N全部初始化）// 查找函数（带路径压缩）
int find(int x) {if (x == fa[x]) return x;else return fa[x] = find(fa[x]);
}// 合并函数：把x和y所在的集合合并
void merge(int x, int y) {int xx = find(x), yy = find(y);if (xx == yy) return;fa[yy] = xx; // 将y的根指向x的根return;
}int main() {int n;cin >> n;// 初始化：fa[i] = ifor (int i = 0; i < N; i++) fa[i] = i;// 处理输入的朋友圈信息for (int i = 0; i < n; i++) {int k, first_;cin >> k; // 该组朋友圈人数for (int j = 0; j < k; j++) {if (j == 0) {cin >> first_;           // 记录第一个人if (st.count(first_) == 0) st[first_] = 1; // 记录这个人出现了} else {int x;cin >> x;               // 输入其余的人if (st.count(x) == 0) st[x] = 1; // 记录新出现的人merge(x, first_);       // 把当前人和第一个人合并（建朋友圈）}}}// 输出所有出现过的人数cout << st.size() << " ";// 统计朋友圈数量（根节点数量）int num = 0;for (int i = 0; i < N; i++) {if (fa[i] == i && st.count(i) != 0) // 是自己父亲+出现过的人num++;}cout << num << endl;// 查询部分int q;cin >> q;while (q--) {int x, y;cin >> x >> y;if (find(x) == find(y)) cout << "Y" << endl; // 在同一个朋友圈else cout << "N" << endl;                    // 不在一个朋友圈}return 0;
}

（4）红色警报

并查集、结构体存储，边失效标记，，计算初始连通快-->计算处理后的 连通快，看看是不是一样，没用什么算法哇

#include <bits/stdc++.h>
using namespace std;// 最大城市数量为 510，最大边数为 5010
const int N = 510, M = 5010;// 并查集数组，fa[i] 表示 i 所属集合的根节点
int fa[N];// 查找集合根节点，同时路径压缩优化
int find(int x) {if (x == fa[x]) return x;return fa[x] = find(fa[x]);
}// 合并两个集合
void merge(int x, int y) {int xx = find(x), yy = find(y);if (xx == yy) return;  // 已在同一集合中fa[xx] = yy;
}// 表示一条边
struct nod {int x, y;       // 连接的两个城市bool flag = false;  // 标记该边是否失效（因为城市被摧毁）
} edge[M];int main() {int n, m;cin >> n >> m;  // 输入城市数量 n 和边的数量 mint landcount = 0;  // 当前的连通块数量（相当于“陆地”数量）// 初始化并查集，每个城市自己是一个集合for (int s = 0; s < n; s++) fa[s] = s;// 输入边并构建初始连通图for (int i = 0; i < m; i++) {cin >> edge[i].x >> edge[i].y;merge(edge[i].x, edge[i].y);}// 统计初始连通块数量for (int s = 0; s < n; s++)if (fa[s] == s) landcount++;int k;cin >> k;  // 输入即将摧毁的城市数量// 开始逐步摧毁城市for (int ss = 0; ss < k; ss++) {int lostcity;cin >> lostcity;  // 当前摧毁的城市编号int nowlandcount = 0;  // 当前连通块数量// 重置并查集for (int s = 0; s < n; s++) fa[s] = s;// 重新构建图，排除已失效的边或涉及当前摧毁城市的边for (int i = 0; i < m; i++) {if (edge[i].flag || edge[i].x == lostcity || edge[i].y == lostcity) {edge[i].flag = true;  // 标记这条边永久失效continue;}merge(edge[i].x, edge[i].y);  // 合并有效边}// 统计当前连通块数量for (int s = 0; s < n; s++)if (fa[s] == s) nowlandcount++;// 判断是否触发红色警报（连通块数增加 2 或更多）if (nowlandcount >= landcount + 2) {cout << "Red Alert: City " << lostcity << " is lost!\n";} else {cout << "City " << lostcity << " is lost.\n";}landcount = nowlandcount;  // 更新连通块数量}// 如果所有城市都被摧毁，游戏结束if (k == n) cout << "Game Over.";return 0;
}

 （5）冗余连接

 

        题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

        从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。如果

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int father[N];// 并查集里寻根的过程
int find(int u) {if(u==father[u]) return u;else return father[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 (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}int main() {int n;cin >> n;//初始化并查集for (int i = 0; i <= n; ++i) {father[i] = i;}for (int i = 0; i < n; i++) {int s,t;cin >> s >> t;if (isSame(s, t)) {  //已经在一个集合里面 输出cout << s << " " << t << endl;return 0;} else {join(s, t);}}
}

边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。输出