Why is my Union Find Disjoint Sets algo for this problem not passing all test cases?

Question

Sample input:

1
3 2
1 2
2 3

First line = # of test cases

First number of second line = number of people

Second number of second line = number of friendships, F

Following F lines = the friendships

Output would be the size of the largest friend group.

So, sample output for that input would be 3. ([1, 2, 3])

My solution:

import java.util.Scanner;
import java.util.HashMap;
import java.util.Collections;

public class Main {

    public static void main (String args[]) {
        Scanner reader = new Scanner(System.in);
        int tests = reader.nextInt();
        for (int i = 0; i < tests; i++) {
            int numcitizens = reader.nextInt();
            // the input is 1-indexed so I create the parent array as such
            int[] parent = new int[numcitizens + 1];
            for (int j = 0; j < (numcitizens + 1); j++) {
                parent[j] = j;
            }
            int[] rank = new int[numcitizens + 1];
            int numpairs = reader.nextInt();
            for (int j = 0; j < numpairs; j++) {
                int A = reader.nextInt();
                int B = reader.nextInt();
                union(A, B, parent, rank);
            }
            HashMap<Integer, Integer> histo = new HashMap<Integer, Integer>();
            for (int j = 1; j < parent.length; j++) {
                int root = parent[j];
                if (!histo.containsKey(root)) {
                    histo.put(root, 1);
                }
                else {
                    histo.put(root, histo.get(root) + 1);
                }

            }
            int max = Collections.max(histo.values());
            System.out.println(max);
        }
    }

    // UFDS find
    static int find(int x, int[] parent) {

        if (parent[x]!= x) {
            parent[x] = find(parent[x], parent);
        }

        return parent[x];
    }

    // UFDS union
    static void union(int x, int y, int[] parent, int[] rank) {
        int xRoot = find(x, parent);
        int yRoot = find(y, parent);

        if (xRoot == yRoot) {
            return;
        }
        else {
            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            }

            else if (rank[yRoot] < rank[xRoot]) {
                parent[yRoot] = xRoot;
            }

            else {
                parent[yRoot] = xRoot;
                for (int i = 0; i < parent.length; i++) {
                    if (parent[i] == yRoot) {
                        parent[i] = xRoot;
                    }
                }
                rank[xRoot] = rank[xRoot] + 1;
            }
        }
    }
}

It works for the sample input, but when passing it through an online judge system that runs it through hundreds of test cases, it tells me wrong output. Not sure where my error might be? Seems like a simple UFDS problem to me.

Answer 1

The for loop you put in union ruins the performance. Just take it out.

In the histogram loop, you need int root = find(j,parent);

Your code throws an exception when numcitizens is zero.

Fix that stuff and your code will work, I think.

Here are a couple extra hints:

• I always union by size instead of union by rank. It has the same complexity, and the size is often useful. In this case you wouldn't need to build the histogram because you'd have the size of every root right there.

• I use a single int[] array for the data structure. If a value v is >=0, then it's a root set with that size (0 means there's no set or empty set at that index). Otherwise ~v is a link to the parent set. I recently used that structure in this answer: Algorithm: use union find to count number of islands