Possible Bipartition

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. 
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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PossibleBipartition {
    public static void main(String[] args) {
        int N = 4;
        int[][] dislikes = { { 1, 2 }, { 1, 3 }, { 2, 4 } };

        System.out.println(possibleBipartition(N, dislikes));
    }

    static boolean possibleBipartition(int N, int[][] dislikes) {
        // Adjacent list
        List<List<Integer>> arr = new ArrayList<List<Integer>>();

        for (int i = 0; i <= N; i++) {
            arr.add(new ArrayList<Integer>());
        }

        // make the graph
        for (int i = 0; i < dislikes.length; i++) {
            int a = dislikes[i][0];
            int b = dislikes[i][1];
            arr.get(a).add(b);
            arr.get(b).add(a);
        }

        // mark all as side -1
        int side[] = new int[N + 1];
        Arrays.fill(side, -1);
        Queue<Integer> q = new LinkedList<Integer>();
        boolean flag = true;

        // iterate for all values
        for (int i = 1; i <= N; i++) {

            // if side is -1
            if (side[i] == -1) {

                // mark side as 0
                side[i] = 0;

                // add into the queue
                q.add(i);

                // iterate till the queue is not empty
                while (!q.isEmpty()) {
                    int curr = q.poll();
                    // Iterate for all adjacent of the current node
                    for (int child : arr.get(curr)) {

                        // if side is -1
                        if (side[child] == -1) {
                            // then mark side as opposite of
                            // the parent
                            side[child] = side[curr] ^ 1;
                            q.add(child);
                        }

                        // else update flag
                        else
                            flag &= side[child] != side[curr];
                    }
                }
            }
        }
        return flag;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool possibleBipartition(int N, vector<vector<int>> &dislikes)
{
    vector<int> arr[N + 1];

    //make the graph
    for (int i = 0; i < dislikes.size(); i++)
    {
        int a = dislikes[i][0];
        int b = dislikes[i][1];
        arr[a].push_back(b);
        arr[b].push_back(a);
    }

    //mark all as side -1
    vector<int> side(N + 1, -1);
    queue<int> q;
    bool flag = true;

    //iterate for all values 
    for (int i = 1; i <= N; i++)
    {

        //if sie is -1
        if (side[i] == -1)
        {

            //mark side as 0
            side[i] = 0;

            //add into the queue
            q.push(i);

            //iterate till the queue is not empty
            while (!q.empty())
            {
                int curr = q.front();
                q.pop();

                //itearte for all adjacent of the current node
                for (int child : arr[curr])
                {

                    //if side is -1
                    if (side[child] == -1)
                    {
                        //then mark side as opposite of
                        //the parent
                        side[child] = side[curr] ^ 1;
                        q.push(child);
                    }

                    //else update flag
                    else
                        flag &= side[child] != side[curr];
                }
            }
        }
    }
    return flag;
}

int main()
{
    int N = 4;
    vector<vector<int>> dislikes = {{1, 2}, {1, 3}, {2, 4}};

    if (possibleBipartition(N, dislikes))
        cout << "true";
    else
        cout << "false";
    return 0;
}