Disjoint set data structure. C++ port of http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/UF.java.html

DisjointSet.cpp

/******************************************************************************
 *  Execution:    ./DisjointSet < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/15uf/tinyUF.txt
 *                http://algs4.cs.princeton.edu/15uf/mediumUF.txt
 *                http://algs4.cs.princeton.edu/15uf/largeUF.txt
 *
 *  Weighted quick-union by rank with path compression.
 *
 *  % ./DisjointSet < tinyUF.txt
 *  4 3
 *  3 8
 *  6 5
 *  9 4
 *  2 1
 *  5 0
 *  7 2
 *  6 1
 *  2 components
 *
 ******************************************************************************/
 // port (sort of) of http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/UF.java.html
 
#include <iostream>

using namespace std;

class DisjointSet
{
public:
	/**
	 * Initializes an empty union–find data structure with {@code n} sites
	 * {@code 0} through {@code n-1}. Each site is initially in its own
	 * component.
	 *
	 * @param  n the number of sites
	 */
	DisjointSet(int n) : n(n)
	{
		parent = new int[n];
		rank = new short[n];
		for (int i = 0; i < n; i++) {
			parent[i] = i;
			rank[i] = 0;
		}
	}
	
	~DisjointSet()
	{
		delete[] parent;
		delete[] rank;
	}

	/**
	 * Returns the component identifier for the component containing site {@code p}.
	 *
	 * @param  p the integer representing one site
	 * @return the component identifier for the component containing site {@code p}
	 */
	int find(int p)
	{
		if (p != parent[p]) {
			parent[p] = find(parent[p]); // path compression
		}
		
		return parent[p];
	}

	/**
	 * Returns the number of components.
	 *
	 * @return the number of components (between {@code 1} and {@code n})
	 */
	int count()
	{
		return n;
	}

	/**
	 * Returns true if the the two sites are in the same component.
	 *
	 * @param  p the integer representing one site
	 * @param  q the integer representing the other site
	 * @return {@code true} if the two sites {@code p} and {@code q} are in the same component;
	 *         {@code false} otherwise
	 */
	bool connected(int p, int q)
	{
		return find(p) == find(q);
	}

	/**
	 * Merges the component containing site {@code p} with the
	 * the component containing site {@code q}.
	 *
	 * @param  p the integer representing one site
	 * @param  q the integer representing the other site
	 */
	void merge(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]++;
		}
		n--;
	}

private:
	int *parent;  // parent[i] = parent of i
	short *rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
	int n;     // number of components
};

/**
 * Reads in a 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 site;
 * if the sites are in different components, merge the two components
 * and print the pair to standard output.
 *
 * @param args the command-line arguments
 */
int main()
{
	int n, p, q;
	cin >> n;
	DisjointSet uf(n);
	while (n--) {
		cin >> p >> q;
		if (uf.connected(p, q)) continue;
		uf.merge(p, q);
		cout << p << " " << q << endl;
	}
	cout << uf.count() << " components" << endl;
}