Graph Coloring Problem
You are given a graph with 'N' vertices numbered from '1' to 'N' and 'M' edges. Your task is to color this graph using two colors, such as blue and red, in a way that no two adjacent vertices (connected by an edge) share the same color.
Input:
The first line of the input contains two integers 'V' and 'E', separated by a space, representing the number of vertices and the number of edges respectively.
The next 'E' lines each contain two integers 'u' and 'v', separated by a space, indicating an edge between vertex 'u' and vertex 'v'.
Output:
Output either "YES" if it is possible to color the graph as described, or "NO" if it is not possible.
Example:
If you are given a graph with vertices and edges as follows:
5 4
1 2
1 3
2 4
3 5
The output should be:
YES
Constraints:
- 1 <= E <= 105
- 1 <= V <= 106
- Time Limit: 1 second
Note:
The given graph may have connected components.
AnswerBot
2d
Graph coloring problem where vertices need to be colored with two colors such that no adjacent vertices share the same color.
Check if the graph can be colored using two colors without any adjacent ver...read more
Help your peers!
Add answer anonymously...
Top Hexaware Technologies Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Hexaware Technologies Software Developer
>
Hexaware Technologies Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app