一 原问题链接

Genealogical tree - POJ 2367 - Virtual Judge

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

二 输入和输出

1 输入

第1行包括整数N，表示火星理事会的成员数。接下来的 N 行，第 i 行包含第 i 个成员的孩子名单。孩子名单可能是空的，名单以 O 结尾。

2 输出

单行输出一系列发言者的编号，用空格分隔。如果有几个序列满足条件，则输出任意一个这样的序列。

三 输入和输出样例

1 输入样例

5

0

4 5 1 0

1 0

5 3 0

3 0

2 输出样例

2 4 5 3 1

四 分析

根据输入样例，构建的图形结构如下图所示，其拓扑序列为 2 4 5 3 1。本问题属于拓扑排序问题，输出拓扑序列即可。

五 代码

package graph.poj2367;

import java.util.Scanner;
import java.util.Stack;

public class Poj2367 {
    static final int maxn = 105;
    static int map[][] = new int[maxn][maxn];
    static int indegree[] = new int[maxn];
    static int topo[] = new int[maxn];
    static int n;
    static Stack<Integer> s = new Stack<>();

    static void TopoSort() { // 拓扑排序
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (indegree[i] == 0)
                s.push(i);
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[++cnt] = u;
            for (int j = 1; j <= n; j++)
                if (map[u][j] == 1)
                    if (--indegree[j] == 0)
                        s.push(j);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            int v;

            while (true) {
                v = scanner.nextInt();
                if (v == 0) {
                    break;
                }
                map[i][v] = 1;
                indegree[v]++;
            }
        }
        TopoSort();
        for (int i = 1; i < n; i++)
            System.out.print(topo[i] + " ");
        System.out.println(topo[n]);
    }
}

六 测试