并查集（Union-Find）是一种数据结构，用于处理一些不交集的合并及查询问题。它主要包含两个操作：
Find：
确定某个元素属于哪个子集。通常是通过递归地查找元素的根节点（即其最终的父节点）来实现。
查找元素x所在的集合的根节点。如果x的父节点是x本身，则x就是根节点；否则，递归地查找x的父节点的父节点，直到找到根节点。
Union：
将两个子集合并成一个。
将两个元素x和y所在的集合合并。首先找到x和y的根节点，然后将其中一个根节点的父节点指向另一个根节点。
表示方法:
模板:
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;
}通过模板，我们可以知道，并查集主要有三个功能。
- 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
- 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
- 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点
模拟过程:
8->3:路径压缩
return u == father[u] ? u : father[u] = find(father[u]);
107. 寻找存在的路径
时间限制：1.000S 空间限制：256MB
题目描述
给定一个包含 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提示信息
数据范围：
1 <= M, N <= 100。
思路:
import java.util.*;
public class Main{
public static void main(String[] args){
int n,l;
Scanner in=new Scanner(System.in);
n=in.nextInt();
l=in.nextInt();
M m= new M(n);
while(l-->0){
m.join(in.nextInt(),in.nextInt());
}
int x=in.nextInt();
int y=in.nextInt();
int result=0;
if( m.isSame(x,y))result=1 ;
System.out.println(result);
}
}
class M{
int[] father;
public M(int n){
father=new int[n+1];
for(int i=1;i<=n;i++){
father[i]=i;
}
}
int find(int i){
if(father[i]==i){
return i;
}
father[i]=find(father[i]);
return father[i];
}
boolean isSame(int i,int j){
i=find(i);
j=find(j);
if(i==j) return true;
return false;
}
void join(int i,int j){
i=find(i);
j=find(j);
if(i==j) return;
father[j]=i;
}
}
