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...
Hexaware Technologies Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter