Colour The Graph
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

Question

Colour The Graph

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

Accepted Answer

The problem is to color a graph with two colors such that no two connected vertices have the same color.

Use a graph coloring algorithm such as Depth First Search (DFS) or Breadth First Search (BFS).
Start with an arbitrary vertex and color it with one color (e.g., blue).
Color all its adjacent vertices with the other color (e.g., red).
Continue this process for all connected components of the graph.
If at any point, you encounter two adjacent vertices with the same color, it is not possible to color the graph as required.
If all vertices are successfully colored without any conflicts, it is possible to color the graph as required.

Accepted Answer

DFS

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’
1. 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’
1. 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.

Space Complexity: OtherExplanation:

O(E), Where E is the edges of the graphs.

In the worst case, we make E number of stack calls. Hence, the overall Space Complexity is O(E).

Time Complexity: OtherExplanation:

O(E + V), Where E and V are the edges and vertices of the graph.

We are traversing through each vertex to check that no two vertices connected by an edge are of the same colour, which takes O(E + V) time. Hence, the overall Time Complexity is O(E + V).

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 :

Input Format :

Output Format :

Constraints :

Top Walmart Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern