<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 Solution {
public:
    class Disjoint
    {
        public:
        vector<int>parent;
        vector<int>rank;

        Disjoint(int n)
        {
            parent.resize(n+1,0);
            rank.resize(n,0);

            for(int i=0;i<n;i++)
            {
                parent[i]=i;
            }
        }

        int findPar(int x)
        {
            if(x==parent[x])
            {
                return x;
            }

            return parent[x]=findPar(parent[x]);
        }

        void Unite(int x,int y)
        {
            int x_=findPar(x);
            int y_=findPar(y);

            if(x_==y_)
            {
                return;
            }

            if(rank[x_]>rank[y_])
            {
                parent[y_]=x_;
            }
            else if(rank[y_]>rank[x_])
            {
                parent[x_]=y_;
            }
            else
            {
                parent[x_]=y_;
                rank[y_]++;
            }
        }
    };
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        Disjoint d(n);

        unordered_map<int,vector<int>>graph;

        for(int i=0;i<dislikes.size();i++)
        {
            graph[dislikes[i][0]].push_back(dislikes[i][1]);
            graph[dislikes[i][1]].push_back(dislikes[i][0]);
        }

        for(auto[key,value]:graph)
        {
            int f=value[0];
            for(int j=1;j<value.size();j++)
            {
                d.Unite(f,value[j]);
            }
        }

        for(auto it:dislikes)
        {
            if(d.findPar(it[0])==d.findPar(it[1]))
            {
                return false;
            }
        }

        return true;

    }
};
77259