- public class UnionFind1 {
- private int[] parent; //数组,表示并查集所有元素的集合号
- private int size; //表示并查集元素个数
- public UnionFind1(int size) { //并查集初始化
- this.size = size;
- parent = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- }
- }
- /**
- * 查看元素所属集合
- *
- * @param element
- * @return
- */
- private int find(int element) {
- return parent[element];
- }
- /**
- * 判断两个集合是否在同一个集合
- *
- * @param firstElement
- * @param secondElement
- * @return
- */
- public boolean isConnected(int firstElement, int secondElement) {
- return find(firstElement) == find(secondElement);
- }
- /**
- * 合并firstElement,secondElement两个元素所在集合
- * 将firstElement集合中所有元素的集合号都变为secondElement,就是认为是将两个集合合并
- *
- * @param firstElement
- * @param secondElement
- */
- public void unionElements(int firstElement, int secondElement) {
- int firstUnion = find(firstElement);
- int secondUnion = find(secondElement);
- if (firstUnion != secondUnion) {
- for (int i = 0; i < size; i++) {
- if (parent[i] == firstUnion) {
- parent[i] = secondUnion;
- }
- }
- }
- }
- private void printArray() {
- for (int id: this.parent) {
- System.out.print(id + "\t");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int n = 10;
- UnionFind1 union = new UnionFind1(n);
- System.out.println("初始:");
- union.printArray();
- System.out.println("连接了5 6");
- union.unionElements(5, 6);
- union.printArray();
- System.out.println("连接了1 2");
- union.unionElements(1, 2);
- union.printArray();
- System.out.println("连接了2 3");
- union.unionElements(2, 3);
- union.printArray();
- System.out.println("连接了1 4");
- union.unionElements(1, 4);
- union.printArray();
- System.out.println("连接了1 5");
- union.unionElements(1, 5);
- union.printArray();
- System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
- System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
- }
- }
快速合并
- public class UnionFind2 {
- private int[] parent;
- private int size;
- public UnionFind2(int size) { //初始化并查集
- this.size = size;
- parent = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- }
- }
- /**
- * 查找element集合的头结点
- * element=parent[element]:说明element元素是一个集合的头结点或者是自己一个集合
- *
- * @param element
- * @return
- */
- public int find(int element) {
- while (element != parent[element]) { //此时说明element已不是自己一个结点了,所以通过循环找寻element所属集合的头结点
- element = parent[element];
- }
- return element; //
- }
- /**
- * 判断两个元素是否是一个集合:只需要判断两个元素所属集合的头结点是否相同即可
- *
- * @param firstElement
- * @param secondElement
- * @return
- */
- public boolean isConnected(int firstElement, int secondElement) {
- int firstUnion = find(firstElement);
- int secondUnion = find(secondElement);
- return firstUnion == secondUnion;
- }
- /**
- * 合并firstElement,secondElement所在的两个集合
- * 将firstElement集合的头结点指向secondElement集合的头结点
- *
- * @param firstElement
- * @param secondElement
- */
- public void unionElements(int firstElement, int secondElement) {
- int firstUnion = find(firstElement);
- int secondUnion = find(secondElement);
- if (firstUnion != secondUnion) {
- parent[firstElement] = secondUnion;
- }
- }
- /**
- * 打印每个元素所属集合的小组号,即它的上一个结点号
- */
- private void printArray() {
- for (int parent: parent) {
- System.out.print(parent + " ");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int n = 10;
- UnionFind2 union = new UnionFind2(n);
- System.out.println("初始:");
- union.printArray();
- System.out.println("连接了5 6");
- union.unionElements(5, 6);
- union.printArray();
- System.out.println("连接了1 2");
- union.unionElements(1, 2);
- union.printArray();
- System.out.println("连接了2 3");
- union.unionElements(2, 3);
- union.printArray();
- System.out.println("连接了1 4");
- union.unionElements(1, 4);
- union.printArray();
- System.out.println("连接了1 5");
- union.unionElements(1, 5);
- union.printArray();
- System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
- System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
- }
- }
快速合并--weight
- public class UnionFind3 {
- private int[] parent;
- private int[] weight;
- private int size;
- public UnionFind3(int size) {
- this.parent = new int[size];
- this.weight = new int[size];
- this.size = size;
- for (int i = 0; i < size; i++) {
- this.parent[i] = i;
- this.weight[i] = 1;
- }
- }
- /**
- * 查找元素所属集合的头结点
- *
- * @param element
- * @return
- */
- public int find(int element) {
- while (element != parent[element]) {
- element = parent[element];
- }
- return element;
- }
- /**
- * 判断两个元素是否是一个集合
- *
- * @param firstElement
- * @param secondElement
- * @return
- */
- public boolean isConnected(int firstElement, int secondElement) {
- return find(firstElement) == find(secondElement);
- }
- public void unionElements(int firstElement, int secondElement) {
- int firstRoot = find(firstElement);
- int secondRoot = find(secondElement);
- if (firstRoot == secondRoot) { //已经是同一个集合的元素就不用再合并了
- return;
- }
- //集合的子元素多的头结点,合并之后仍然做头结点
- if (weight[firstRoot] > weight[secondRoot]) {
- parent[secondRoot] = firstRoot;
- weight[firstRoot] += weight[secondRoot];
- } else {
- parent[firstRoot] = secondRoot;
- weight[secondRoot] += weight[firstRoot];
- }
- }
- /**
- * 打印parent数组
- */
- public void printArray(int[] arr) {
- for (int parent: arr) {
- System.out.print(parent + "\t");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int n = 10;
- UnionFind3 union = new UnionFind3(n);
- System.out.println("初始parent:");
- union.printArray(union.parent);
- System.out.println("初始weight:");
- union.printArray(union.weight);
- System.out.println("连接了5 6 之后的parent:");
- union.unionElements(5, 6);
- union.printArray(union.parent);
- System.out.println("连接了5 6 之后的weight:");
- union.printArray(union.weight);
- System.out.println("连接了1 2 之后的parent:");
- union.unionElements(1, 2);
- union.printArray(union.parent);
- System.out.println("连接了1 2 之后的weight:");
- union.printArray(union.weight);
- System.out.println("连接了2 3 之后的parent:");
- union.unionElements(2, 3);
- union.printArray(union.parent);
- System.out.println("连接了2 3 之后的weight:");
- union.printArray(union.weight);
- System.out.println("连接了1 4 之后的parent:");
- union.unionElements(1, 4);
- union.printArray(union.parent);
- System.out.println("连接了1 4 之后的weight:");
- union.printArray(union.weight);
- System.out.println("连接了1 5 之后的parent:");
- union.unionElements(1, 5);
- union.printArray(union.parent);
- System.out.println("连接了1 5 之后的weight:");
- union.printArray(union.weight);
- System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
- System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
- }
- }
快速合并--height
- public class UnionFind4 {
- private int[] parent;
- private int[] height;
- int size;
- public UnionFind4(int size) {
- this.size = size;
- this.parent = new int[size];
- this.height = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- height[i] = 1;
- }
- }
- public int find(int element) {
- while (element != parent[element]) {
- element = parent[element];
- }
- return element;
- }
- public boolean isConnected(int firstElement, int secondElement) {
- return find(firstElement) == find(secondElement);
- }
- public void unionElements(int firstElement, int secondElement) {
- int firstRoot = find(firstElement);
- int secondRoot = find(secondElement);
- if (firstRoot == secondRoot) {
- return;
- }
- if (height[firstRoot] > height[secondRoot]) {
- parent[secondRoot] = firstRoot;
- } else if (height[firstRoot] < height[secondRoot]) {
- parent[firstRoot] = secondRoot;
- } else {
- parent[firstRoot] = secondRoot;
- height[secondRoot] += 1;
- }
- }
- private void printArray(int[] arr) {
- for (int parent: arr) {
- System.out.print(parent + " ");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int n = 10;
- UnionFind4 union = new UnionFind4(n);
- System.out.println("初始parent:");
- union.printArray(union.parent);
- System.out.println("初始height:");
- union.printArray(union.height);
- System.out.println("连接了5 6 之后的parent:");
- union.unionElements(5, 6);
- union.printArray(union.parent);
- System.out.println("连接了5 6 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 2 之后的parent:");
- union.unionElements(1, 2);
- union.printArray(union.parent);
- System.out.println("连接了1 2 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了2 3 之后的parent:");
- union.unionElements(2, 3);
- union.printArray(union.parent);
- System.out.println("连接了2 3 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 4 之后的parent:");
- union.unionElements(1, 4);
- union.printArray(union.parent);
- System.out.println("连接了1 4 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 5 之后的parent:");
- union.unionElements(1, 5);
- union.printArray(union.parent);
- System.out.println("连接了1 5 之后的height:");
- union.printArray(union.height);
- System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
- System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
- }
- }
路径压缩
- public class UnionFind5 {
- private int[] parent;
- private int[] height;
- int size;
- public UnionFind5(int size) {
- this.size = size;
- this.parent = new int[size];
- this.height = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- height[i] = 1;
- }
- }
- public int find(int element) {
- while (element != parent[element]) {
- parent[element] = parent[parent[element]]; //对于height比较大的,可以压缩路径
- element = parent[element];
- }
- return element;
- }
- public boolean isConnected(int firstElement, int secondElement) {
- return find(firstElement) == find(secondElement);
- }
- public void unionElements(int firstElement, int secondElement) {
- int firstRoot = find(firstElement);
- int secondRoot = find(secondElement);
- if (firstRoot == secondRoot) {
- return;
- }
- if (height[firstRoot] > height[secondRoot]) {
- parent[secondRoot] = firstRoot;
- } else if (height[firstRoot] < height[secondRoot]) {
- parent[firstRoot] = secondRoot;
- } else {
- parent[firstRoot] = secondRoot;
- height[secondRoot] += 1;
- }
- }
- private void printArray(int[] arr) {
- for (int parent: arr) {
- System.out.print(parent + " ");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int n = 10;
- UnionFind5 union = new UnionFind5(n);
- System.out.println("初始parent:");
- union.printArray(union.parent);
- System.out.println("初始height:");
- union.printArray(union.height);
- System.out.println("连接了5 6 之后的parent:");
- union.unionElements(5, 6);
- union.printArray(union.parent);
- System.out.println("连接了5 6 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 2 之后的parent:");
- union.unionElements(1, 2);
- union.printArray(union.parent);
- System.out.println("连接了1 2 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了2 3 之后的parent:");
- union.unionElements(2, 3);
- union.printArray(union.parent);
- System.out.println("连接了2 3 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 4 之后的parent:");
- union.unionElements(1, 4);
- union.printArray(union.parent);
- System.out.println("连接了1 4 之后的height:");
- union.printArray(union.height);
- System.out.println("连接了1 5 之后的parent:");
- union.unionElements(1, 5);
- union.printArray(union.parent);
- System.out.println("连接了1 5 之后的height:");
- union.printArray(union.height);
- System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
- System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
- }
- }
例题
例题:How Many Tables
- public class Main {
- private int[] parent;
- private int[] weight;
- private int size;
- private int groups;
- public Main(int size) {
- this.size = size;
- this.groups = size;
- this.parent = new int[size];
- this.weight = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- weight[i] = 1;
- }
- }
- public int find(int element) {
- while (element != parent[element]) {
- element = parent[element];
- }
- return element;
- }
- public boolean isConnected(int firstElement, int secondElement) {
- return find(firstElement) == find(secondElement);
- }
- public void unionElement(int firstElement, int secondElement) {
- int firstRoot = find(firstElement);
- int secondRoot = find(secondElement);
- if (firstRoot == secondRoot) {
- return;
- }
- if (weight[firstRoot] < weight[secondRoot]) {
- parent[firstRoot] = secondRoot;
- weight[secondRoot] += weight[firstRoot];
- } else {
- parent[secondRoot] = firstRoot;
- weight[firstRoot] += weight[secondRoot];
- }
- this.groups--;
- }
- public int getGroups() {
- return this.groups;
- }
- public void printArray(int[] arr) {
- for (int parent: arr) {
- System.out.print(parent + " ");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- Scanner scan = new Scanner(System. in );
- int n = scan.nextInt();
- for (int i = 0; i < n; i++) {
- int N = scan.nextInt();
- Main m = new Main(N);
- int M = scan.nextInt();
- for (int j = 0; j < M; j++) {
- int a = scan.nextInt() - 1;
- int b = scan.nextInt() - 1;
- m.unionElement(a, b);
- }
- System.out.println(m.getGroups());
- }
- }
- }