Just need a pseudo code, not the entire run code. Give the modifications needed to either the DFS algorithm so that it can check if the vertices in a graph can be labeled with 0's and 1's such that there is not an edge between vertices with the same label.

CodePudding user response：

The graph that you are looking for is called a Bipartite graph. A modification to DFS would be like this (let color[node] be -1 in the beginning for all nodes):

• let color[1] = 1.
• start DFS from node 1
• inside your DFS color all uncolored neighbors of the current node with a color opposite to the color of the current node.
• if there exists a colored neighbor with color equal to current node's color then there is no solution.