刷题记录
*并查集理论基础
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;
}