Hackerrank's Merging Communities

Challenge can be found here


People connect with each other in a social network. A connection
between Person I and Person J is represented as M I J. When two persons
belonging to different communities connect, the net effect is the
merger of both communities which I and J belongs to.


At the beginning, there are N people representing N communities. Suppose
person 1 and 2 connected and later 2 and 3 connected, then 1,2, and 3 will
belong to the same community.


There are two type of queries:


M I J => communities containing person I and J merged (if they belong to
different communities).


Q I => print the size of the community to which person belongs.


Input Format


The first line of input will contain integers N and Q, i.e. the number
of people and the number of queries. The next Q lines will contain the
queries.


Constraints :


1 <= N <= 100000


1 <= Q <= 200000

My code times out for 6 / 9 test-cases, so obviously this can be improved a lot.

Any suggestions would be much appreciated.

```
import java.io.*;
import java.util.*;

class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int Q = s.nextInt();
DisjointSet ds = new DisjointSet();

for(int i = 1; i >> disjointSet;

DisjointSet() {
disjointSet = new ArrayList>>();
}

public void makeSet(int element) {
Map> map = new HashMap<>();
Set set = new HashSet<>();
set.add(element);
map.put(element, set);
disjointSet.add(map);
}

public void union(int a, int b) {
int first = find(a);
int second = find(b);
Set firstSet = null;
Set secondSet = null;

for(int i = 0; i > map = disjointSet.get(i);
if(map.containsKey(first)) {
firstSet = map.get(first);
} else if(map.containsKey(second)) {
seco

Simplifying

for(int i = 0; i > map = disjointSet.get(i);
            if(map.containsKey(first)) {
                firstSet = map.get(first);
            } else if(map.containsKey(second)) {
                secondSet = map.get(second);
            }
        }

Consider instead

for (Map> map : disjointSet) {
            if (firstSet == null) {
                firstSet = map.get(first);
            }

            if (secondSet == null) {
                secondSet = map.get(second);
            }

            if (firstSet != null && secondSet != null) {
                break;
            }
        }

You don't need i. Java can iterate over a collection directly, which saves us a line of code.

You don't need to check containsKey before doing get. If containsKey is false, then get will return null.

You might as well stop as soon as both sets are found. You don't need to keep going.

A linear scan over all the values is something like \$\mathcal{O}(N \cdot Q)\$, assuming the number of merges is proportional to the number of queries. Because you have to do one linear scan for each merge. However, there is an alternative solution that is closer to \$\mathcal{O}(Q)\$.

Alternative data structure

DisjointSet ds = new DisjointSet();

Consider

DisjointSet ds = new DisjointSet(N + 1);

Now you can change from

private List>> disjointSet;

to something fixed size. The normal representation for a disjoint set is a parent pointer tree with ranks added. In this case, we need to track the sizes and can use those to represent the rank. Consider

public class DisjointSet {

    private int[] parents;
    private int[] sizes;

    DisjointSet(int N) {
        parents = new int[N];
        sizes = new int[N];
    }

    public void makeSet(int i) {
        parents[i] = i;
        sizes[i] = 1;
    }

    public void union(int a, int b) {
        int first = find(a);
        int second = find(b);

        // if already part of the same set, no need to union
        if (first == second) {
            return;
        }

        if (sizes[first] < sizes[second]) {
            parents[first] = second;
            sizes[second] += sizes[first];
        } else {
            parents[second] = first;
            sizes[first] += sizes[second];
        }
    }

    public int find(int i) {
        // if not the root
        if (parents[i] != i) {
            // Make the parent the root, so that it will recurse at most once
            // on subsequent calls.
            parents[i] = find(parents[i]);
        }

        // Return the root (as the parent is always the root by this point).
        return parents[i];
    }

    public int getSetSize(int i) {
        return sizes[find(parents[i])];
    }

}

The parents array stores the immediate parent of any element. If an element is alone in a set, it is its own parent. Root nodes (terminators) are also their own parents.

For a root node, the sizes array holds the size of the set. For other nodes, it holds junk data.

This uses both union-by-rank and path compression for an optimal runtime. It's also reasonably efficient in space, requiring only two integers for each element.

StackExchange Code Review Q#157757, answer score: 4