Last Updated: 16 Mar, 2021
Possible Bipartition
Moderate
Asked in companies
You are given an integer ‘N’ which denotes a set of N people numbered from 1 to N and a matrix ‘DISLIKE’ with M rows and 2 columns. Each row in the matrix denotes two people who dislike each other i.e. for any valid row i, DISLIKE[i][0] dislikes DISLIKE[i][1] and vice versa.
Your task is to split the set of N people into two groups under the conditions:
1. It is not allowed to put two persons in the same group who dislike each other.
2. The size of the two groups may or may not be equal.
3. Each person from the set belongs to exactly one group.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line of each test case contains two integers ‘N’ and ‘M’, which denotes the number of people in the given set and the number of rows of the matrix ‘DISLIKE’.
The next M lines contain two integers, DISLIKE[i][0] and DISLIKE[i][1], denoting the two people who dislike each other.
Output Format:
For each test case, print a single line containing 1 if it is possible to split everyone into two groups under the given conditions otherwise print 0.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1<= T <= 10
1 <= N <= 2000
0 <= M <= 5000
DISLIKE[i].size = 2
1 <= DISLIKE[i][0],DISLIKE[i][1] <=N
DISLIKE[i][0] != DISLIKE[i][1], for any valid i
Where ’T’ is the number of test cases, and N denotes the number of people in the set’, M denotes the size of the given matrix ‘DISLIKE’.
Time Limit: 1 sec.
Approaches
The idea is to represent the given problem as a graph.
We will create a graph in which each person is represented by a node and there is an undirected edge between all pairs of people who dislike each other.Then we will assign one of the two colors(0 or 1) to every vertex using graph traversal algorithms such that no two adjacent vertices have the same color. It means we are dividing the set of people into two parts. The first group of people has representative color 1 and the second group of people has representative color 2. Whenever assigning color creates a conflict, it means it is not possible to divide the set of N people into two groups. We are using Depth-First Search for this.
The steps are as follows:
- Make an undirected graph named ‘graph’ from the given matrix ‘dislike’.
- Initialize a 2-D vector/list of integers of size N + 1.
- Iterate from i = 0 to dislike.size() - 1, ie. iterate through the matrix ‘dislike’:
- Let the first element of the current row be denoted by ‘a’ and the second element of the current row be denoted by ‘b’.
- Append ‘b’ at the end of graph[a] ’.
- Append ‘a’ at the end of graph[b].
- Initialize an array ‘colors’ of size N+1 with -1 in all the indices, which denotes the representative color of all the set of persons. For example,
- if colors[2] = 0, it means Person 2 has representative color as ‘0’.
- if colors[2] = 1, it means Person 2 has representative color as ‘1’.
- if colors[2] = -1, it means the representative color of Person 2 is not decided yet.
- Iterate from i = 1 to N for all the people:
- If color is already assigned to the person ie. color[i] != -1, continue.
- Otherwise, perform a Depth-first Search starting from the ith vertex.
- Define a boolean recursive function dfs which takes four arguments, ‘currentVertex’, ‘graph’, ‘colors’, and ‘parentColor’, which denotes the current vertex which we have to assign a color, the graph that we created using the given matrix ‘dislike’, and color that we have assigned to the parent of the current vertex. If the function returns true, it means that we can divide the current component into 2 groups. If it returns false, it means that we can not divide the current component into 2 groups. So, return false.
- As each component is independent of other components, it means initially we can start with any color 0 or 1. Let’s start with 0 and set parent color to 1.
- Assign a color to the current vertex as the opposite of the parent vertex ie. 1 - color of parent vertex.
- Iterate through all the adjacent vertices(say vertex x) of the current vertex :
- If the color of the vertex x is the same as the color of the currentVertex, it means that it is impossible to divide the group into two parts. So, return 0.
- Otherwise, call the recursive function dfs with arguments x, graph, colors, and color of the current vertex.
- If this function returns false, it means that it is impossible to divide the group into two parts. So, return 0.
- If we successfully complete the coloring all the adjacent vertices of the current vertex, it means this component of the graph can be colored successfully. So, return true.
- If we can not divide at least one of the components, it means that we can not divide the set of N people into two groups. So, return false.
- If all the recursive calls return true, it means that we can divide the set of N people into 2 groups under the given conditions. So, return true.