并查集：
一个简单的leetcode图论题为例：1971. 寻找图中是否存在路径
class Solution {
int[] father;
public boolean validPath(int n, int[][] edges, int source, int destination) {
father = new int[n];
init();
for (int i = 0; i < edges.length; i++) {
join(edges[i][0], edges[i][1]);
}
return isSame(source, destination);
}
// 并查集初始化
public void init() {
for (int i = 0; i < father.length; i++) {
father[i] = i;
}
}
// 并查集里寻根的过程
public int find(int u) {
if (u == father[u]) {
return u;
} else {
father[u] = find(father[u]);
return father[u];
}
}
// 判断 u 和 v是否找到同一个根
public boolean isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 将v->u 这条边加入并查集
public 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)，就是判断两个节点是不是同一个根节点。