* The union–find data type models a collection of sets containing * n elements, with each element in exactly one set. * The elements are named 0 through n–1. * Initially, there are n sets, with each element in its * own set. The canonical element of a set * (also known as the root, identifier, * leader, or set representative) * is one distinguished element in the set. Here is a summary of * the operations: *
* The canonical element of a set can change only when the set * itself changes during a call to union—it cannot * change during a call to either find or count. *
* This implementation uses weighted quick union by rank * with path compression by halving. * The constructor takes Θ(n) time, where * n is the number of elements. * The union and find operations take * Θ(log n) time in the worst case. * The count operation takes Θ(1) time. * Moreover, starting from an empty data structure with n sites, * any intermixed sequence of m union and find * operations takes O(m α(n)) time, * where α(n) is the inverse of * Ackermann's function. *
* For alternative implementations of the same API, see * {@link QuickUnionUF}, {@link QuickFindUF}, and {@link WeightedQuickUnionUF}. * For additional documentation, see * Section 1.5 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class UF { private int[] parent; // parent[i] = parent of i private byte[] rank; // rank[i] = rank of subtree rooted at i (never more than 31) private int count; // number of components /** * Initializes an empty union-find data structure with * {@code n} elements {@code 0} through {@code n-1}. * Initially, each element is in its own set. * * @param n the number of elements * @throws IllegalArgumentException if {@code n < 0} */ public UF(int n) { if (n < 0) throw new IllegalArgumentException(); count = n; parent = new int[n]; rank = new byte[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } } /** * Returns the canonical element of the set containing element {@code p}. * * @param p an element * @return the canonical element of the set containing {@code p} * @throws IllegalArgumentException unless {@code 0 <= p < n} */ public int find(int p) { validate(p); while (p != parent[p]) { parent[p] = parent[parent[p]]; // path compression by halving p = parent[p]; } return p; } /** * Returns the number of sets. * * @return the number of sets (between {@code 1} and {@code n}) */ public int count() { return count; } /** * Returns true if the two elements are in the same set. * * @param p one element * @param q the other element * @return {@code true} if {@code p} and {@code q} are in the same set; * {@code false} otherwise * @throws IllegalArgumentException unless * both {@code 0 <= p < n} and {@code 0 <= q < n} * @deprecated Replace with two calls to {@link #find(int)}. */ @Deprecated public boolean connected(int p, int q) { return find(p) == find(q); } /** * Merges the set containing element {@code p} with the set * containing element {@code q}. * * @param p one element * @param q the other element * @throws IllegalArgumentException unless * both {@code 0 <= p < n} and {@code 0 <= q < n} */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // make root of smaller rank point to root of larger rank if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ; else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP; else { parent[rootQ] = rootP; rank[rootP]++; } count--; } // validate that p is a valid index private void validate(int p) { int n = parent.length; if (p < 0 || p >= n) { throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1)); } } /** * Reads an integer {@code n} and a sequence of pairs of integers * (between {@code 0} and {@code n-1}) from standard input, where each integer * in the pair represents some element; * if the elements are in different sets, merge the two sets * and print the pair to standard output. * * @param args the command-line arguments */ public static void main(String[] args) { int n = StdIn.readInt(); UF uf = new UF(n); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.find(p) == uf.find(q)) continue; uf.union(p, q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + " components"); } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/