Possible Bi-partition Leetcode Solution

Welcome back to the daily Leetcode series! We have yet another graph problem ahead of us today, and it's not as easy as the last one so pull up your socks!

Understanding The Problem

The problem description has once again been twisted to make it even more difficult to identify the topic this problem belongs to.

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

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Let's take a look at a few examples.

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].

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

Let's map out this problem to an abstraction. Forget about the people mentioned, who dislikes whom, and anything related to the physical world. Now, what we have left is a set of numbers, and a set of constraints saying which numbers can't be grouped. Does this remind you of any particular data structure?

Intuition

Map out the numbers to nodes, the dislikes array to edges between these nodes, and voila! We have a graph on our hands. Now, think about the constraint given. We need to separate the nodes into two groups such that no two nodes in the same group will have an edge between them.

Let's visualize the first example to make the problem statement crystal clear.

In this graph, we can divide the nodes into two sets, (1,4) and (2,3). As you can see, any two nodes in the same group do not have any edges between them.

This graph requires you to know about something known as a bipartite graph. Without this key concept, it's not possible to solve this problem.

Formally, a bipartite graph is a graph that can be divided into two sets of vertices, such that no two vertices within the same set are connected by an edge. More formally, a graph is bipartite if it is possible to partition its vertices into two disjoint sets X and Y, such that every edge in the graph connects a vertex in X to a vertex in Y. If this sounds too complicated, that's because it kind of is.

But, for this problem, all you need to know is that we need to divide the nodes into two groups, such that any two nodes in the same group do not have an edge between them.

Where there's a graph problem, there almost always is a traversal solution. We will be using BFS to solve this problem. We need to check if the given graph is bipartite or not.

We'll follow the following algorithm:

1. Make an adjacency matrix from the given dislikes input array.

2. Initialize a group array of size n with -1, that will store which group each node is in.

3. Iterate through all the nodes. For each unassigned node, run a BFS with the node as the source.

4. Assign group 1 to the source node.

5. Inside the BFS loop, assign all the unassigned neighbors of the current node with the alternate group index (=0).

6. For all the neighbors that have already been assigned a group, check if the assigned group of the current node is the same as the group assigned to the neighbor. If so, return false.

7. Return true once the loop ends.

Coding Up The Solution

Here's the full solution to this problem.

class Solution {
public:
    bool util(vector<vector<int>>& graph,vector<int>& group,int src){
        group[src] = 1;
        queue<int> q;
        q.push(src);

        while(!q.empty()){
            int t = q.front();
            q.pop();

            for(int i = 1; i < group.size(); i++){
                if(graph[t][i] and group[i] == -1){
                    group[i] = 1 - group[t];
                    q.push(i);
                }
                else if(graph[t][i] and group[i] == group[t]){
                    return false;
                }
            }
        }
        return true;
    }
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(n+1,vector<int>(n+1,0));
        for(vector<int> i : dislikes){
            graph[i[0]][i[1]] = 1;
            graph[i[1]][i[0]] = 1;
        }

        vector<int> group(n+1,-1);

        for(int i = 1; i < n; i++){
            if(group[i] == -1){
                if(!util(graph,group,i)) return false;
            }
        }
        return true;
    }
};

The reason we loop through all the nodes in the possibleBipartition function is to deal with the edge case of a disconnected graph. We perform BFS on all the connected components of the graph.

That's it for today! Hope you understood this problem. Come back tomorrow for another analysis of an interesting problem.

Cheers!