java - 图着色算法 : typical scheduling problem

Question

我正在训练像 UvA 这样的代码问题，我有一个必须做的问题，给定一组 n 考试和 k 名学生参加考试，看看是否可以将所有考试安排在两个时间段。

输入几个测试用例。每一个都以包含 1 < n < 200 要安排的不同考试的一行开始。第 2 行有 k 的案例数，其中至少有 1 名学生参加了 2 次考试。接下来是 k 行，每行包含 2 个数字，用于指定上述每个案例的一对检查。(n = 0 的输入将意味着输入结束并且不被处理)。

输出:您必须决定考试计划是否可能 2 个时间段。

例子:

输入:

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

输出:

NOT POSSIBLE.
POSSIBLE.

我认为一般的方法是图形着色，但我真的是一个新手，我可以承认我在理解这个问题时遇到了一些困难。无论如何，我正在尝试这样做然后提交它。有人可以帮我为这个问题做一些代码吗？我现在必须处理和理解这个算法，以便以后一遍又一遍地使用它。

我更喜欢 C 或 C++，但如果你愿意，Java 对我来说没问题；)

提前致谢

Answer 1

你是正确的，这是一个图形着色问题。具体来说，您需要确定图形是否可二次着色。这很简单:在图上做一个 DFS，交替着色黑色和白色节点。如果发现冲突，则该图不是 2-colorable，并且无法进行调度。

possible = true

for all vertex V
  color[V] = UNKNOWN

for all vertex V
  if color[V] == UNKNOWN
    colorify(V, BLACK, WHITE)

procedure colorify(V, C1, C2)
  color[V] = C1
  for all edge (V, V2)
    if color[V2] == C1
      possible = false
    if color[V2] == UNKNOWN
      colorify(V2, C2, C1)

这在 O(|V| + |E|) 中运行，带有邻接表。