PROBLEM LINK:
Author: Manish Pathak
Tester: Manish Pathak
Editorialist: Manish Pathak
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory,Bipartite Graph
PROBLEM:
In Mirzapur,there is a gang of kaleen bhaiya.Due to some reasons the gang split into different small groups.
Some of them joined Guddu bhaiya and some kaleen bhaiya. Two of the gang leaders decided that the whole Gang will be divided in such a way that no two friends exist in the same gang.But they are not intelligent enough to do the task. So you have to do this for them.
There were N number of people in the gang [1,2,…N] and many of them are friends to each other.You have given the friend list.You have to determine that it is possible to divide them in such a manner or not.
EXPLANATION:
According to the problem it is clear that we have to divide the group in such a way that there will not be any connection in the same group.e.g. Suppose 1 and 2 are friends and 1 and 3 are friends,Now if we will make two sets then in the first Set there will be only 1 and in the second set 2 and 3 because 2 and 3 are not friends to each other.
By using bipartite graph we can easily solve this problem.
BIPARTITENESS CHECK
Let’s use a series of breadth-first searches, starting from each vertex which hasn’t been visited yet. In each search, assign the vertex from which we start to side 1. Each time we visit a yet unvisited neighbor of a vertex assigned to one side, we assign it to the other side. When we try to go to a neighbor of a vertex assigned to one side which has already been visited, we check that is has been assigned to the other side; if it has been assigned to the same side, we conclude that the graph is not bipartite. Once we’ve visited all vertices and successfully assigned them to sides, we know that the graph is bipartite and we have constructed its partitioning.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here