代码随想录Day69(图论Part05)

并查集

// 1.初始化
int fa[MAXN];
void init(int n)
{for (int i=1;i<=n;++i)fa[i]=i;
}// 2.查询
找到的祖先直接返回，未进行路径压缩
int.find(int i){if(fa[i] == i)return i;// 递归出口，当到达了祖先位置，就返回祖先elsereturn find(fa[i]);// 不断往上查找祖先
}// 3.合并
void unionn(int i,int j)int i_fa=find(i);// 找到i的祖先    int j_fa=find(j);// 找到j的祖先fa[i_fa]=j_fa;// i的祖先指向j的祖先。
}

路径压缩，也就是在某一次find函数执行过程中，更新子节点的指向，直接指向顶级节点

107.寻找存在的路径

题目：107. 寻找存在的路径 (kamacoder.com)

思路：难道说，使用并查集的find函数，遍历所有的边，将节点的父亲信息存起来，如果source和destination没有指向同一个根节点，那么就说明不存在路径

尝试（不对)

import java.util.*;class Main{public static int n;public static int m;public static int[] fa;public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();fa = new int[n];for(int i = 0; i<n; i++){fa[i] = i;}for(int i = 0; i<m; i++){int n1 = scanner.nextInt();int n2 = scanner.nextInt();union(n1,n2);}int source = scanner.nextInt();int destination = scanner.nextInt();if(source == find(destination)){System.out.println(1);}else{System.out.println(0);}}public static void union(int i , int j){int i_fa = find(i);int j_fa = find(j);fa[i_fa] = j_fa;}public static int find(int j){if(j==fa[j])return j;else{fa[j] = find(fa[j]);return fa[j];}}
}

答案

import java.util.Scanner;public class Main {private static int[] father;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 节点数量int m = scanner.nextInt(); // 边的数量// 初始化并查集father = new int[n + 1];init(n);// 读取边并构建并查集for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();join(s, t);}int source = scanner.nextInt(); // 起始节点int destination = scanner.nextInt(); // 目标节点// 判断是否在同一个集合中if (isSame(source, destination)) {System.out.println(1);} else {System.out.println(0);}}// 并查集初始化private static void init(int n) {for (int i = 1; i <= n; i++) {father[i] = i;}}// 并查集里寻根的过程private static int find(int u) {if (u != father[u]) {father[u] = find(father[u]);}return father[u];}// 判断 u 和 v 是否找到同一个根private static boolean isSame(int u, int v) {return find(u) == find(v);}// 将 v -> u 这条边加入并查集private static void join(int u, int v) {int rootU = find(u);int rootV = find(v);if (rootU != rootV) {father[rootV] = rootU;}}
}

小结