java - 用于解决冲突的分组算法

Question

来自谷歌的算法题:

一位老师想把他的问题学生分成两组。他有一个名字列表(成对)，代表不能归入同一组的学生。我们的任务是检查是否可以在不发生碰撞的情况下将所有学生分开。

例如，如果列表是:

Jack Jim (cannot be in the same group)
Jim Rose (...)
Rose Jack (...)

那么不发生碰撞就不可能将它们全部分开。

我的思路是利用graph的思想，用associate array或者map来实现。但是，我觉得如果图有很多不相连的分支，会很复杂。谁能帮忙？

Answer 1

您想检查该图是否是二分图。 Wikipedia有关于如何操作的详细信息。

这是一个related SO question和一个 Java implementation来自普林斯顿。