*算法训练（leetcode）第四十七天 | 并查集理论基础、107. 寻找存在的路径
刷题记录
- *并查集理论基础
- 107. 寻找存在的路径
*并查集理论基础
讲解
107. 寻找存在的路径
题目地址
直接套模板。
结点编号从1开始，因此定义father数组时需要n+1个空间，否则会越界。
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
// c++
#include<bits/stdc++.h>
using namespace std;// 初始化
void init(vector<int> &father){for(int i=0; i<father.size(); i++) father[i] = i;
}
// 查找所在并查集的根节点
int find(vector<int> &father, int u){if(u == father[u]) return u;return father[u] = find(father, father[u]);// return father[u];
}
// 判断两节点是否在同一并查集
bool isSame(vector<int> &father, int u, int v){u = find(father, u);v = find(father, v);return u == v;
}// 把v加入u
void join(vector<int> &father, int u, int v){u = find(father, u);v = find(father, v);if(u == v) return;father[v] = u;
}int main(){int n, m, s, t, src, des;cin>>n>>m;vector<int> father(n+1, 0);init(father);for(int i=0; i<m; i++){cin>>s>>t;join(father, s, t);}cin>>src>>des;cout<<isSame(father, src, des);return 0;
}