### PROBLEM LINK:

**Editorialist**: Lalit Kundu

### DIFFICULTY:

EASY

### PRE-REQUISITES:

Graphs, Graph coloring, BFS

### PROBLEM:

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.

### EXPLANATION:

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.