并查集理论基础
并查集常用来解决连通性问题。就是判断两个元素是否在同一个集合里的时候,我们就要想到用并查集。
主要功能:
- 将两个元素添加到一个集合中。
- 判断两个元素在不在同一个集合
步骤:
初始化:father[]来存储每个节点的父节点,初始化时将父节点设为自己,father[i]=i
查询:find(i),递归查找找i的祖先,找到了就返回祖先,否则不断往上找。return find(father[u])
- 路径压缩:并查集只需判断各个节点祖先节点是否相同,因此不用考虑2,3,4节点直接是否有关系,所以才可以路径压缩。return father[u] = find(father[u])
合并:union/join(u,v),分别找到u的祖先和v的祖先,u=find(u),v=find(v),如果不是同一个,让u做v的祖先,father[v]=u。一句话,join(u,v)就是让u的祖先做v祖先的祖先
判断是否同一根:isSame(u,v)方法,return find(u)==find(v)
模版:
package second.chapter11_graph_theory;
/**
* @author 毕晶
* @date 2024/7/18 14:56
*/
public class UnionFind {
private int[] father;
private int n;
//初始化并查集
public UnionFind(int n) {
this.n = n;
father = new int[n];
init();
}
//并查集初始化
private void init() {
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
// 并查集里寻根的过程
private int find(int u) {
return father[u] == u ? u : (father[u] = find(father[u]));
}
// 判断 u 和 v是否找到同一个根
public boolean isSame(int u, int v) {
return find(u) == find(v);
}
// 将v->u 这条边加入并查集
public void join(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
father[v] = u;
}
}
public static void main(String[] args) {
int n = 1005;
UnionFind uf = new UnionFind(n);
//测试join和isSame方法
uf.join(1, 2);
uf.join(2, 3);
System.out.println(uf.isSame(1, 3));
System.out.println(uf.isSame(1, 4));
uf.join(3, 4);
System.out.println(uf.isSame(1, 4));
}
}
107.寻找存在的路径
题目链接:107.寻找存在的路径
文档讲解:代码随想录
状态:做出来了
思路:并查集常用来解决连通性问题。就是判断两个元素是否在同一个集合里的时候,我们就要想到用并查集。
题解:
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取节点数量
int m = scanner.nextInt(); // 读取边的数量
UnionFind uf = new UnionFind(n + 1); // 初始化并查集,节点编号从1开始,所以大小为n+1
for (int i = 0; i < m; i++) {
int u = scanner.nextInt(); // 读取边的一个端点
int v = scanner.nextInt(); // 读取边的另一个端点
uf.join(u, v); // 将这条边加入并查集
}
int source = scanner.nextInt(); // 读取起点
int destination = scanner.nextInt(); // 读取终点
// 判断起点和终点是否在同一个连通分量中
System.out.println(uf.isSame(source, destination) ? 1 : 0);
}
static class UnionFind {
private int[] father; // 存储每个节点的父节点
private int n; // 节点的数量
public UnionFind(int n) {
this.n = n;
father = new int[n]; // 初始化父节点数组
init(); // 调用初始化方法
}
// 并查集初始化
private void init() {
for (int i = 0; i < n; i++) {
father[i] = i; // 每个节点的父节点初始化为自己
}
}
// 并查集里寻根的过程,带路径压缩
private int find(int u) {
return father[u] == u ? u : (father[u] = find(father[u]));
}
// 将 v->u 这条边加入并查集
public void join(int u, int v) {
u = find(u); // 寻找 u 的根
v = find(v); // 寻找 v 的根
if (u != v) { // 如果 u 和 v 的根不同,则合并
father[v] = u; // 将 v 的根连接到 u 的根
}
}
// 判断 u 和 v 是否找到同一个根
public boolean isSame(int u, int v) {
return find(u) == find(v);
}
}
}