<p>There is an <strong>undirected</strong> graph with <code>n</code> nodes, where each node is numbered between <code>0</code> and <code>n - 1</code>. You are given a 2D array <code>graph</code>, where <code>graph[u]</code> is an array of nodes that node <code>u</code> is adjacent to. More formally, for each <code>v</code> in <code>graph[u]</code>, there is an undirected edge between node <code>u</code> and node <code>v</code>. The graph has the following properties:</p>

<ul>
	<li>There are no self-edges (<code>graph[u]</code> does not contain <code>u</code>).</li>
	<li>There are no parallel edges (<code>graph[u]</code> does not contain duplicate values).</li>
	<li>If <code>v</code> is in <code>graph[u]</code>, then <code>u</code> is in <code>graph[v]</code> (the graph is undirected).</li>
	<li>The graph may not be connected, meaning there may be two nodes <code>u</code> and <code>v</code> such that there is no path between them.</li>
</ul>

<p>A graph is <strong>bipartite</strong> if the nodes can be partitioned into two independent sets <code>A</code> and <code>B</code> such that <strong>every</strong> edge in the graph connects a node in set <code>A</code> and a node in set <code>B</code>.</p>

<p>Return <code>true</code><em> if and only if it is <strong>bipartite</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1,3],[0,2],[1,3],[0,2]]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can partition the nodes into two sets: {0, 2} and {1, 3}.</pre>

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

<ul>
	<li><code>graph.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= graph[u].length &lt; n</code></li>
	<li><code>0 &lt;= graph[u][i] &lt;= n - 1</code></li>
	<li><code>graph[u]</code>&nbsp;does not contain&nbsp;<code>u</code>.</li>
	<li>All the values of <code>graph[u]</code> are <strong>unique</strong>.</li>
	<li>If <code>graph[u]</code> contains <code>v</code>, then <code>graph[v]</code> contains <code>u</code>.</li>
</ul>

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
    //     int n = graph.size();
    //     queue<int> qu;
    //     unordered_map<int, int> mp0, mp1;
    //     vector<int> vis(n, 0);
    //     for(int x = 0; x < n; x++)
    //     {   
    //         if(vis[x] == 0)
    //         {
    //             int flag = 1;
    //             qu.push(x);
    //             vis[x] = 1;
    //             for(auto i: graph[x])
    //             mp0[i] = 1;
    //             while(!qu.empty())
    //             {
    //                 int k = qu.size();
    //                 for(int i = 0; i < k; i++)
    //                 {
    //                     int node = qu.front();
    //                     qu.pop();
    //                     for(auto i: graph[node])
    //                     {
    //                         if(vis[i] == 0)
    //                         {
    //                             if(flag == 1)
    //                             {   if(mp1.find(i) == mp1.end())
    //                                 {
    //                                     for(auto j: graph[i])
    //                                     mp1[j] = 1;
    //                                 }
    //                                 else
    //                                 return false;
    //                             }
    //                             else
    //                             {   if(mp0.find(i) == mp0.end())
    //                                 {
    //                                     for(auto j: graph[i])
    //                                     mp0[j] = 1;
    //                                 }
    //                                 else
    //                                 return false;
    //                             }
    //                             vis[i] = 1;
    //                             qu.push(i);
    //                         }
    //                     }
    //                 }
    //                 if(flag == 1) flag = 0;
    //                 else flag = 1;
    //             }
    //         } 
    //     }
    // return true;
    
        int n = graph.size();
        queue<int> qu;
        set<int> mp0, mp1;
        vector<int> vis(n, 0);
        for(int x = 0; x < n; x++)
        {   
            if(vis[x] == 0)
            {
                int flag = 1;
                qu.push(x);
                vis[x] = 1;
                for(auto i: graph[x])
                mp0.insert(i);
                while(!qu.empty())
                {
                    int k = qu.size();
                    for(int i = 0; i < k; i++)
                    {
                        int node = qu.front();
                        qu.pop();
                        for(auto i: graph[node])
                        {
                            if(vis[i] == 0)
                            {
                                if(flag == 1)
                                {   if(mp1.count(i) == 0)
                                    {
                                        for(auto j: graph[i])
                                        mp1.insert(j);
                                    }
                                    else
                                    return false;
                                }
                                else
                                {   if(mp0.count(i) == 0)
                                    {
                                        for(auto j: graph[i])
                                        mp0.insert(j);
                                    }
                                    else
                                    return false;
                                }
                                vis[i] = 1;
                                qu.push(i);
                            }
                        }
                    }
                    if(flag == 1) flag = 0;
                    else flag = 1;
                }
            } 
        }
    return true;
    }
};
17000