一 原问题链接

Labeling Balls - POJ 3687 - Virtual Judge

https://vjudge.net/problem/POJ-3687

二 输入和输出

1 输入

第1行包含测试用例的数量。每个测试用例的第1行都包含两个整数N和M，分别表示球的数量和约束的数量。后面的M行，每行都包含两个整数a和b，表示标签为a的球比标签为b的球轻。在每个测试用例前都有一个空行。

2 输出

对于每个测试用例，都单行输出标签1~N的球的重量。如果存在多个解决方案，则输出标签为1的球的最小重量，然后输出标签为2的球的最小重量，以此类推，如果不存在解，则输出-1。

三 输入和输出样例

1 输入样例

5

4 0

4 1

1 1

4 2

1 2

2 1

4 1

2 1

4 1

3 2

2 输出样例

1 2 3 4

-1

-1

2 1 3 4

1 3 2 4

四 分析

本问题不是输出小球的标签，而是按标签输出小球的重量，而且标签小的球的重量尽可能小。

1 示例一

输入以下数据。
5 4

5 1

4 2

1 3

2 3

构建图的图形如下。

根据重量关系，先输出3，然后输出2，然后输出4，然后输出1，最后输出5。

2 示例二

输出以下数据
10 5

4 1

8 1

7 8

4 1

2 8

根据重量关系。标签1到10的球的重量分别为： 5 1 6 2 7 8 3 4 9 10

五 算法设计

可采用两种解决方案。

1 建立正向图

i从n到1，j从n到1，检查第1个出度为0的点t，分配重量w[t]=i,将弧尾节点的出度减1，继续下一个循环。若没有出度为0的节点，则说明有环，退出。

2 建立反向图

建立原图的逆向图。i从n到1，j从n到1，检查第1个入度为0的节点t，分配重量w[t]=i,将其邻接点的入度减1，继续下一个循环。若没有入度为0的几点，则说明有环，退出。

六 代码

package graph.poj3687;

import java.util.Scanner;

public class Poj3687 {
    static final int maxn = 205;
    static int map[][];
    static int in[];
    static int w[] = new int[maxn];
    static int n;
    static int m;
    static int T;
    static int u;
    static int v;
    static boolean flag;

    static void TopoSort() { // 拓扑排序
        flag = false;
        for (int i = n; i > 0; i--) {
            int t = -1;
            for (int j = n; j > 0; j--)
                if (in[j] == 0) {
                    t = j;
                    break;
                }
            if (t == -1) { // 有环
                flag = true;
                return;
            }
            in[t] = -1;
            w[t] = i;
            for (int j = 1; j <= n; j++)
                if (map[t][j] == 1)
                    in[j]--;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();

        while (T-- > 0) {
            map = new int[maxn][maxn];
            in = new int[maxn];
            n = scanner.nextInt();
            m = scanner.nextInt();

            for (int i = 1; i <= m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                if (map[v][u] == 0) { // 建立逆向图，检查重复边
                    map[v][u] = 1;
                    in[u]++;
                }
            }
            TopoSort();
            if (flag) {
                System.out.println(-1);
                continue;
            }
            for (int i = 1; i < n; i++)
                System.out.print(w[i] + " ");
            System.out.println(w[n]);
        }
    }
}

七 测试