并查集理论基础
背景
当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。
并查集主要有两个功能：
- 将两个元素添加到一个集合中。
- 判断两个元素在不在同一个集合
原理讲解
从代码层面，我们如何将两个元素添加到同一个集合中呢。
只需要用一个一维数组来表示，即：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;
}我们的目的是判断这三个元素是否在同一个集合里，知道 A 连通 B 就已经足够了。
这里要讲到寻根思路，只要 A ，B，C 在同一个根下就是同一个集合。
给出A元素，就可以通过 father[A] = B，father[B] = C，找到根为 C。
给出B元素，就可以通过 father[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。
// 并查集里寻根的过程
int find(int u) {
if (u == father[u]) return u; // 如果根就是自己，直接返回
else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}我们需要 father[C] = C，即C的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。
所以father数组初始化的时候要 father[i] = i，默认自己指向自己。
// 并查集初始化
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;
}路径压缩
在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根。
如果这棵多叉树高度很深的话，每次find函数 去寻找根的过程就要递归很多次。
我们的目的只需要知道这些节点在同一个根下就可以，所以对这棵多叉树的构造只需要这样就可以了，除了根节点其他所有节点都挂载根节点下，这样我们在寻根的时候就很快，只需要一步，如果我们想达到这样的效果，就需要 路径压缩，将非根节点的所有节点直接指向根节点。
我们只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。
因为 find 函数向上寻找根节点，father[u] 表述 u 的父节点，那么让 father[u] 直接获取 find函数 返回的根节点，这样就让节点 u 的父节点 变成根节点。
// 并查集里寻根的过程
int find(int u) {
if (u == father[u]) return u;
else return father[u] = find(father[u]); // 路径压缩
}并查集主要有三个功能。
- 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
- 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
- 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点
107. 寻找存在的路径
题目描述
给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
输入描述
第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
输出描述
输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。
输入示例
5 4
1 2
1 3
2 4
3 4
1 4
输出示例
1
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father=vector<int>(101,0);
void init(){
for(int i=1;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;
father[v]=u;
}
int main(){
int m,s,t,ss,d;
cin>>n>>m;
init();
while(m--){
cin>>s>>t;
join(s,t);
}
cin>>ss>>d;
if(isSame(ss,d))cout<<1<<endl;
else cout<<0<<endl;
}