Possible Bipartition

Problem

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

Constraints:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 104
• dislikes[i].length == 2
• 1 <= ai < bi <= n
• All the pairs of dislikes are unique.

Solution

class Solution {
    int[] root;
    int[] rank;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        // transform the input into an adjacency list
        var adj = new ArrayList<List<Integer>>();

        root = new int[n + 1];
        rank = new int[n + 1];

        for (var i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<>());
            root[i] = i;
            rank[i] = 1;
        }

        for (var d : dislikes) {
            adj.get(d[0]).add(d[1]);
            adj.get(d[1]).add(d[0]);
        }

        for (var i = 0; i < n; i++) {
            var node = adj.get(i);

            for (var x = 0; x < node.size(); x++) {
                var neighbor = node.get(x);
                if (find(i) == find(neighbor)) {
                    return false;
                }
                union(node.get(0), neighbor);
            }
        }

        return true;
    }

    int find(int x) {
        if (root[x] != x) {
            root[x] = find(root[x]);
        }
        return root[x];
    }

    void union(int x, int y) {
        var rootX = find(x);
        var rootY = find(y);
        if (rank[rootX] > rank[rootY]) {
            //swap
            rootX ^= rootY;
            rootY ^= rootX;
            rootX ^= rootY;
        }
        rank[rootY] += rank[rootX];
        root[rootX] = rootY;
    }
}