I ended up solving this using a disjoint set, as many others have. However, I have a question about the performance of an alternate "brute-force" approach I'm hoping to get some guidance on. N.B. am using Java 8.

I first attempted to solve this using a "brute-force" approach: (1) maintaining a map from person ID integers to hashsets of person IDs, (2) merging (or "unioning") friend circles by copying the contents of a source hashset to a target one, and (3) updating entries in the hashmap for each member of a source hashset. This worked out well for all of the test cases except the 10th, where it timed out. I downloaded the test case, which has 100k queries, and, sure enough, my solution would begin to bog down around 50k iterations.

Has anyone else run into this problem using this approach, or does anyone have any insight into what the performance bottleneck is? Is it simply that the "union" operation of copying the contents of one hashset to another is too expensive? Is it a problem with Java's Hash{Set,Map} slowing down as more entries are added? I can understand why this approach would be slower than a disjoint-set approach, but I'm a little surprised by how bad the performance is.

Here's a sketch of the solution (excluding the "get biggest friend circle" component). I tried several variations of the code below, without luck, including experimenting with setting the initial capacities and load factors of the hash-based data structures, and make sure to merge smaller friend circles into larger ones.

import java.util.*;

class Solution {
    static Map<Integer, Set<Integer>> buildCircles(int[][] queries) {
        Map<Integer, Set<Integer>> friendCircleByPersonId = new HashMap<>();
        Stack<Integer> inNeedOfFriendCircle = new Stack<>();
        Stack<Set<Integer>> friendCircles = new Stack<>();

        for (int[] query : queries) {
            for (int personId : query) {
                if (friendCircleByPersonId.containsKey(personId)) {
                    friendCircles.push(friendCircleByPersonId.get(personId));
                } else {
                    inNeedOfFriendCircle.push(personId);
                }
            }

            if (friendCircles.isEmpty())
                friendCircles.push(new HashSet<>());

            Set<Integer> friendCircle0 = friendCircles.pop();

            while (!inNeedOfFriendCircle.isEmpty()) {
                int personId = inNeedOfFriendCircle.pop();
                friendCircle0.add(personId);
                friendCircleByPersonId.put(personId, friendCircle0);
            }

            while (!friendCircles.isEmpty()) {
                Set<Integer> friendCircleN = friendCircles.pop();

                for (int personId : friendCircleN) {
                    friendCircle0.add(personId);
                    friendCircleByPersonId.put(personId, friendCircle0);
                }
            }
        }

        return friendCircleByPersonId;
    }
}