'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Colour The Graph

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
25 upvotes
Asked in companies
Samsung R&D InstituteHCL TechnologiesMakeMyTrip

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
 Constraints :
1 <= E <= 10 ^ 5
1 <= V <= 10 ^ 6

Time Limit: 1 sec
Sample Input 1 :
4 4
1 2
2 3
3 4
4 1
Sample Output 1 :
YES
Explanation for Sample 1 :
One possible coloring of the graph is:

col_graph

Sample Input 2 :
3 3
1 2
2 3
3 1
Sample Output 2 :
NO
Full screen
Console