javaalgorithmdisjoint-setsunion-finddisjoint-union

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

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.

Solution

  • 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: