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

<p>Given the integer <code>n</code> and the array <code>dislikes</code> where <code>dislikes[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that the person labeled <code>a<sub>i</sub></code> does not like the person labeled <code>b<sub>i</sub></code>, return <code>true</code> <em>if it is possible to split everyone into two groups in this way</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2000</code></li>
	<li><code>0 &lt;= dislikes.length &lt;= 10<sup>4</sup></code></li>
	<li><code>dislikes[i].length == 2</code></li>
	<li><code>1 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= n</code></li>
	<li>All the pairs of <code>dislikes</code> are <strong>unique</strong>.</li>
</ul>

class DJ {
public:
    DJ(int N) : N(N) {
        init();
    }
    vector<int> parent, rank, count, point;

    void init() {
        parent.resize(N);
        rank.resize(N);
        count.resize(N);
        point.resize(N);
        for (int i=0; i<N; i++) {
            parent[i] = i;
            rank[i] = 0;
            count[i] = 1;
            point[i] = 0;
        }
    }

    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }

    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] < rank[v]) {
            parent[u] = v;
            count[v] += count[u];
        }
        else {
            parent[v] = u;
            count[u] += count[v];
        }
    }

    int getCount(int i) {
        int parent = find(i);
        return count[parent];
    }

    int getPoint(int i) {
        int parent = find(i);
        return point[parent];
    }
    void addPoint(int i, int val) {
        int parent = find(i);
        point[parent] += val;
    }
private:
    int N;
};

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& a) {
        // point 1, 2, ..., n
        // point NOT:
        //       n+1,n+2,...n+n
        DJ dj(2 * n + 2);
        for (auto e : a) {
            dj.join(e[0], e[1] + n);
            dj.join(e[0] + n, e[1]);
        }
        for (int u = 1; u <= n; u++) {
            if (dj.find(u) == dj.find(u + n)) return false;
        }
        return true;
    }
};
63615