图着色算法:典型的调度问题

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

你是对的,这是一个图形着色问题.具体而言,您需要确定图形是否为2色.这是微不足道的:在图表上做一个DFS,为交替的黑白节点着色.如果发现冲突,则图形不是2可着色的,并且调度是不可能的.

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|)与邻接列表一起运行.

Answer 2

我已将polygenelubricant的伪代码翻译为JAVA代码，以便为我的问题提供解决方案。我们有一个提交平台（如 uva/ACM 竞赛），所以我知道即使在更多、最难的情况下它也通过了。

这里是：

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;

/**
 *
 * @author newba
 */
public class GraphProblem {

    class Edge {
        int v1;
        int v2;

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }
    }

    public GraphProblem () {
        Scanner cin = new Scanner(System.in);

        while (cin.hasNext()) {

            int num_exams = cin.nextInt();
            if (num_exams == 0)
                break;
            int k = cin.nextInt();
            Hashtable<Integer,String> exams = new Hashtable<Integer, String>();
            ArrayList<Edge> edges = new ArrayList<Edge>();
            for (int i = 0; i < k; i++) {
                int v1 = cin.nextInt();
                int v2 = cin.nextInt();
                exams.put(v1,"UNKNOWN");
                exams.put(v2,"UNKNOWN");
                //add the edge from A->B and B->A
                edges.add(new Edge(v1, v2));
                edges.add(new Edge(v2, v1));
            }

            boolean possible = true;
            for (Integer key: exams.keySet()){
                if (exams.get(key).equals("UNKNOWN")){
                    if (!colorify(edges, exams,key, "BLACK", "WHITE")){
                        possible = false;
                        break;
                    }
                }
            }

            if (possible)
                System.out.println("POSSIBLE.");
            else
                System.out.println("NOT POSSIBLE.");

        }
    }

    public boolean colorify (ArrayList<Edge> edges,Hashtable<Integer,String> verticesHash,Integer node, String color1, String color2){

        verticesHash.put(node,color1);
        for (Edge edge : edges){
            if (edge.v1 == (int) node) {
                if (verticesHash.get(edge.v2).equals(color1)){
                    return false;
                }
                if (verticesHash.get(edge.v2).equals("UNKNOWN")){
                    colorify(edges, verticesHash, edge.v2, color2, color1);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        new GraphProblem();
    }
}

我还没有优化，我没有时间重新开始，但如果你愿意，你/我们可以在这里讨论。

希望你喜欢它！;)