Last Updated: 7 Jul, 2016
Colour The Graph
Moderate
Asked in companies
You are given a graph with 'N' vertices numbered from '1' to 'N' and 'M' edges. You have to colour this graph in two different colours, say blue and red such that no two vertices connected by an edge are of the same colour.
Note :
The given graph may have connected components.
Input Format :
The first line of input contains two integers 'V' and 'E', separated by a single space. They denote the total number of vertices and edges respectively.
From the second line onwards, the next 'E' lines represent an edge between the two vertices.
Every edge is represented by two vertices(u, v) that share an edge between them. The values of the vertices would again be separated by a single space.
Output Format :
Print "YES" if it is possible else print "NO".
Constraints :
1 <= E <= 10 ^ 5
1 <= V <= 10 ^ 6
Time Limit: 1 sec
Approaches
We can approach this problem by running a DFS starting from vertex-1.
We have a total of ‘m’ edges.
When can we achieve the configuration when we see in reference to vertex-1?
- Let's say vertex-1 is ‘Blue’
- If all the vertices that connect to vertex-1 are ‘Red’, then we can say that the configuration is possible.
- If this would be the negation of the last one. Say, vertex-1 is ‘Red’
- If all the vertices that connect to vertex-1 are ‘Blue’, then we can say that the configuration is possible.
The above idea can be extended further in a Depth First manner to check the above condition on every vertex possible.