---
description: Bipartite Graph Check
---

# 5.Possible Bipartition

A **Bipartite Graph** is a graph whose vertices can be divided into two independent sets, **U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U.**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MJR2Py5SLYu5Je6MNBS%2F-MJR3-hPwNgWffDuCGuU%2Fbipartitegraph-1.jpg?alt=media\&token=d0a0d3f0-08de-40ba-a79c-3e1369f11f2b)

### Question:

Given a set of `N` people (numbered `1, 2, ..., N`), we would like to split everyone into two groups of **any** size.\
Each person may dislike some other people, and they should not go into the same group.&#x20;

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

Return `true` if and only 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: group1 [1,4], group2 [2,3]

Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
```

## Solution : (Check for Bipartite Graph using Color)

```cpp
class Solution
{
public:
    bool checkBipartite(int itr, vector<int> v[], vector<bool> &vs, vector<int> &col)
    {

        queue<int> q;
        q.push(itr);
        vs[itr] = 1;
        col[itr] = 1;

        while (!q.empty())
        {
            int node = q.front();
            int colr = col[node];
            q.pop();
            
            for (int i = 0; i < v[node].size(); i++)
            {
                if (vs[v[node][i]] == 0)
                {
                    q.push(v[node][i]);
                    vs[v[node][i]] = 1;
                    col[v[node][i]] = 1 - colr;
                }
                else
                {
                    if (col[v[node][i]] == colr)
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    bool possibleBipartition(int n, vector<vector<int>> &dislikes)
    {

        vector<int> v[n + 1];
        vector<bool> vs(n + 1);
        vector<int> col(n + 1, -1);
        for (int i = 0; i < dislikes.size(); i++)
        {
            v[dislikes[i][0]].push_back(dislikes[i][1]);
            v[dislikes[i][1]].push_back(dislikes[i][0]);
        }

        for (int i = 1; i <= n; i++)
        {
            if (vs[i] == 0)
            {
                if (!checkBipartite(i, v, vs, col))
                {
                    return false;
                }
            }
        }

        return true;
    }
};
```
