笔记：代码随想录算法训练营day60：并查集理论基础、寻找存在的路径

本文为学习并查集理论基础 | 代码随想录、代码随想录过程中的思考

find是找的顶头上司，而不是当前上司，最后怎么也得找到一个顶头上司的上司是自己，要不然这个结构也不成立

使用issame替换会使被操作者为当前节点，而非根节点。join(u,v)的功能为将v的根节点挂到u的根节点下

模拟过程可以看出，join中的find中的路径压缩要在长度大于2（路径大于1）的时候才会体现出来

107. 寻找存在的路径

卡码网题目链接（ACM模式）

使用并查集的模板，主要把该连的线（边）连一下，然后如果二位是同一领导就可以判断在同一合集了，能连上线，就是所谓的有路径

#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<int> father=vector<int>(101,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;    //不要误写为u=father[v];
    }
}
int main(){
    int m,s,t,source,destination;
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        cin>>s>>t;
        join(s,t);
    }
    cin>>source>>destination;
 
    if (isSame(source,destination)==true) cout<<1<<endl;
    else{
        cout<<0<<endl;
    }
    return 0;
}