hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Possible Bipartition


  • Approach:

    1. The first thing is creating a bi-directed graph.

    2. The problem said to partition the people into two groups where they do not like each other.

    3. That means coloring the graph with two different colors.

    4. To store the color status initiate a visited array which initially remains uncolored -1 for all the nodes.

    5. Now start traversing for each of the nodes from 1 to N.

    6. And try to color all the nodes in the path with two different colors.

    7. Start with a node i. And color it with 0.

    8. The adjacent node should be able to color with color 1. If it is not possible then return false.

    9. Else color the nodes, And go for other nodes as well.

    10. Return true at the end, as it is possible to color them using two different colors.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:


bool dfs(int src, vector<vector<int>>&graph, vector<int>&visited, int color){

visited[src] = color;

bool status = true;

for(int i=0; i<graph[src].size(); i++){

int child = graph[src][i];

if(visited[child] != -1 && visited[child] == color) status = status & false;

if(visited[child] == -1) status = status & dfs(child, graph, visited, color ^ 1);

}

return status;

}


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

vector<vector<int>>graph(n+1);

int dis_size = dislikes.size();

for(int i=0; i<dis_size; i++){

graph[dislikes[i][0]].push_back(dislikes[i][1]);

graph[dislikes[i][1]].push_back(dislikes[i][0]);

}

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

for(int i=1; i<=n; i++){

if(visited[i] == -1){

if(!dfs(i, graph, visited, 0)) return false;

}

}

return true;

}

};