Editorialist: Lalit Kundu
Graphs, Graph coloring, BFS
You are given a undirected graph with K(<500) nodes. You need to split graph into two sets such that no two nodes in a set share an edge. If it’s not possible to do so, report that.
We pick up any node and assign it to any arbit set(say A). Naturally, all it’s immediate neighbors should belong to set B and all neighbors of these immediate neighbors will belong to the set A and so on…
So, we’ll do a breadth first search from source node and keep on assigning opposite colors to immediate neighbors. During BFS, for a node u, if we encounter already colored immediate neighbor, we assert that it’s of opposite color, else it is not possible to break nodes into two sets in required way.
Complexity: O(K), using adjacency lists.
O(K*K) using adjacency matrix.
See editorialist’s detailed solution for implementation details.