树相关
发表评论
并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者 某个元素 和 另一个元素是否同属于一个集合。可以用于点的分堆、判断点的互相可达性。
/** * @Author: Sumail-Lee * @Date: 2019/1/4 15:57 * @Description: 将一个集合内的点分堆,每个分好堆的点内都互相可达,公用同一个爹 */ public class 并查集 { private int[] parent; private int size; public 并查集(int size) { this.size = size; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } public int findParent(int element) { while (element != parent[element]) { element = parent[element]; } return element; } public boolean isConnected(int firstElement, int secondElement) { return findParent(firstElement) == findParent(secondElement); } public void unionElements(int firstElement, int secondElement) { int firstRoot = findParent(firstElement); int secondRoot = findParent(secondElement); if (firstRoot == secondRoot) { return; } parent[firstRoot] = secondRoot; } }