[Interview type questions] Divide friends into two groups, and people in the same group do not know each other

Input: Give edges to represent their relations.
Output: Divide the friends into two groups, and people in the same group do now know each other.

Example: Give 4 persons. [0, 1] [1, 2] [1, 3]
         0 and 1 know each other, 1 and 2 know each other...
         We can take 0,2 as group 1 and 1,3 as group 2.

Solution: Use bipartite graph with BFS to resolve this problem:

  int n = 4;
  int[][] relations = new int[][] { { 0, 1 }, { 1, 2 }, { 2, 3 } };

  // Build a graph and initialize groups
  HashMap<Integer, Set<Integer>> graph = new HashMap<>();
  int[] group = new int[4];
  Arrays.fill(group, -1);
  for (int[] edge : relations) {
   Set neighbors = graph.getOrDefault(edge[0], new HashSet<>());
   neighbors.add(edge[1]);
   graph.put(edge[0], neighbors);
  }
  // BFS, start with 0
  Queue queue = new LinkedList<>();
  queue.offer(0);
  int groupdId = 0;
  group[0] = groupdId;
  while(queue.isEmpty() == false) {
   int v = queue.poll();
   groupdId = 1 - group[v];
   // Get its neighbors
   // No neighbors..
   if (graph.get(v) == null) continue;
   for (int neighbor : graph.get(v)) {
    if (group[neighbor] == -1) {
     group[neighbor] = groupdId;
     queue.offer(neighbor);
    } else if (group[neighbor] == group[v]) {
     // It cannot be divided into two group. Invalid bipartite graph
     break;
    }
   }
  }
  
  for (int g : group) {
   System.out.println(g);
  }