并查集理论基础
背景：判断连通性，即两个元素是否在同一个集合里/如何将两个元素放入同一个集合里
原理：一维数组，用father连根
两种优化方式：路径压缩，按秩合并
代码模板：
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) {
return u == father[u] ? u : 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;
}寻找存在的路径
注意：
不需要grid，变成father
cin变成join，前面要init()
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int N = 1005;
vector<int> father = vector<int>(N, 0);
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]); //?
}
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;
}
else {
father[v] = u;
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
init(); //!!!!
// vector<list<int>> grid(n + 1);
for (int i = 0; i < m; i++) {
cin >> s >> t;
join(s, t); // !!!!
}
int source, dest;
cin >> source >> dest;
bool result = isSame(source, dest);
if (result) {
cout << 1 << endl;
}
else {
cout << 0 << endl;
}
return 0;
}