题目详情

考察点：图、拓扑序列。
给定一个有向无环图和它的一系列点序列，输出属于其拓扑序列的点序列索引。

我的版本

暴力求解，即对于当前序列的当前判断点A，判断有无未取出的点指向当前点A，时间复杂度为，有个实例不能AC。实现过程中踩的坑主要是nextInt读取数据，如果判断不符条件，注意要将当前行的数据全部读取出来。这道题用BufferedReader可能更合适。此外，这道题在记录边的时候取巧了，将点的值作为点的索引，使用int矩阵存储边。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() + 1;   // 顶点数
        int m = sc.nextInt();       // 边数
        int[][] eg = new int[n][n];
        for (int i = 0; i < m; i ++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            eg[x][y] = 1;           // x -> y
        }
        sc.nextLine();              // nextInt与nextLine切换时需要注意一点【nextInt读取数之后将光标放在同一行；nextLine读取到\n，并将光标放到下一行】
        int k = Integer.parseInt(sc.nextLine());       // 序列数
        String rs = "";
        for (int i = 0; i < k; i ++) {
            int[] b = new int[n];                      // 记录对应点是否已取出
            int t = 1;
            String[] line = sc.nextLine().split(" ");
            for (t = 0; t < n-1; t ++) {
                int x = Integer.parseInt(line[t]);
                for (int j = 1; j < n; j ++) {
                    if (b[j] == 0 && eg[j][x] == 1) {  // 点未排出且能指向当前排出的点
                        t = n - 1;
                        break;
                    }
                }
                b[x] = 1;
            }
            if (t == n) {
                if (rs.length() == 0) {
                    rs = "" + i;
                } else {
                    rs += " " + i;
                }
            }
        }
        System.out.println(rs);
    }
}

参考版本

PAT平台的代码效率评估可能不是很准确吧，C++同样的思路就可以全部AC……

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, a, b, k, flag = 0, in[1010];
    vector<int> v[1010];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        in[b]++;
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int judge = 1;
        vector<int> tin(in, in+n+1);
        for (int j = 0; j < n; j++) {
            scanf("%d", &a);
            if (tin[a] != 0) judge = 0;
            for (int it : v[a]) tin[it]--;
        }
        if (judge == 1) continue;
        printf("%s%d", flag == 1 ? " ": "", i);
        flag = 1;
    }
    return 0;
}