Onderdeel van Microsoft
Actieve werkgever
Sollicitatievraag bij LinkedIn
Design a function to determine whether a graph is bipartite.
Antwoord op sollicitatievraag
Anoniem
19 mrt 2012
User BFS for same, while traversing through nodes label the first visited node as 0, label its neighbors as 1. if you get a label 1 node, label its unlabelled neighbors as 0. at any point if you get an already labelled neighbor as 0 - 0 ( you get label 0 neighbor from label 0 node) or 1 - 1(respectively) the graph is not bipartite