并查集理论基础
题目链接/文章讲解:并查集理论基础 | 代码随想录
寻找存在的路径
题目链接/文章讲解:代码随想录
java">import java.util.*;public class Main {public static void main(String[] args) {int numberOfElements, numberOfConnections;Scanner scanner = new Scanner(System.in);// 读取元素数量和连接数量numberOfElements = scanner.nextInt();numberOfConnections = scanner.nextInt();// 初始化并查集DisjointSetUnion disjointSet = new DisjointSetUnion(numberOfElements + 1);// 读取每对连接并合并for (int i = 0; i < numberOfConnections; ++i) {int elementA = scanner.nextInt();int elementB = scanner.nextInt();disjointSet.union(elementA, elementB);}// 检查两个元素是否在同一集合中int queryElementA = scanner.nextInt();int queryElementB = scanner.nextInt();if (disjointSet.isConnected(queryElementA, queryElementB)) {System.out.println("1"); // 在同一集合} else {System.out.println("0"); // 不在同一集合}}
}// 并查集实现
class DisjointSetUnion {private int[] parent;public DisjointSetUnion(int size) {parent = new int[size];// 初始化每个元素的父节点为自己for (int i = 0; i < size; ++i) {parent[i] = i;}}// 查找元素的根节点,并进行路径压缩public int find(int element) {if (element != parent[element]) {parent[element] = find(parent[element]); // 路径压缩}return parent[element];}// 合并两个元素的集合public void union(int elementA, int elementB) {int rootA = find(elementA);int rootB = find(elementB);if (rootA != rootB) {parent[rootB] = rootA; // 将B的根节点指向A的根节点}}// 检查两个元素是否在同一集合中public boolean isConnected(int elementA, int elementB) {return find(elementA) == find(elementB);}
}