uandf.java

/*Seeyeon Oh
 * 251205169*/
public class uandf{
    private int[] parent;
    private int[] rank;
    private int numSets;

    // Constructor
    public uandf(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        numSets = n;
        for (int i = 1; i <= n; i++) {
            make_Set(i);
        }
    }

    // Make set operation
    public void make_Set(int i) {
        parent[i] = i;
        rank[i] = 0;
    }

    // Find set operation with path compression
    public int find_Set(int i) {
        if (parent[i] != i) {
            parent[i] = find_Set(parent[i]); // Path compression
        }
        return parent[i];
    }

    // Union sets operation with union by rank
    public void union_Sets(int i, int j) {
        int iRoot = find_Set(i);
        int jRoot = find_Set(j);

        if (iRoot == jRoot) return; // Already in the same set

        // Attach smaller rank tree under root of higher rank tree
        if (rank[iRoot] < rank[jRoot]) {
            parent[iRoot] = jRoot;
        } else if (rank[iRoot] > rank[jRoot]) {
            parent[jRoot] = iRoot;
        } else {
            // If ranks are the same, make one as root and increment its rank by one
            parent[jRoot] = iRoot;
            rank[iRoot]++;
        }
        numSets--; // Decrease the number of sets
    }

    // Final sets operation
    public int final_Sets() {
        int representative = 1;
        for (int i = 1; i < parent.length; i++) {
            // Only interested in the representative (root) of each set
            if (parent[i] == i) {
                parent[i] = representative++; // Assign new representative
            } else {
                // Path compression
                parent[i] = find_Set(parent[i]);
            }
        }
        int totalSets = numSets;
        numSets = 0; // Reset the number of sets
        return totalSets;
    }

    // Main method to demonstrate the usage
    public static void main(String[] args) {
	uandf ds = new uandf(10); // Create 10 disjoint sets
        ds.union_Sets(2, 4);
        ds.union_Sets(5, 6);
        ds.union_Sets(1, 3);
        System.out.println("Set representative of 4: " + ds.find_Set(4));
        System.out.println("Set representative of 6: " + ds.find_Set(6));
        System.out.println("Total sets: " + ds.final_Sets());
    }
}