Feature #4: Split Users into Two Groups

Description

In this feature, the company has decided that they want to show people “follow” recommendations. For this purpose, we have been given the “following” relationship information for a group of users in the form of a graph. We want to see if these people can be split into two groups such that no one in the group follows or is followed-by anyone in the same group. We will then recommend people from the same group to each other.

The “following” relationship graph is given in the form of an undirected graph. So, if UserA follows UserB, or the other way around, it does not matter. This graph will be given to us as an input in the form of a 2D array called graph. In this array, each graph[i] will contain a list of indices, j, for which the edge between nodes i and j exists. Each node in the graph will represent a person and will be denoted by an integer ID from 0 to graph.length-1.

For example, the graph can be [[3], [2, 4], [1], [0, 4], [1, 3]]. This can be illustrated as: