首页 编程题 PAT

# 题目描述

题目链接

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

pic

# Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.

# Output Specification:

Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.

# Sample Input:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
6
5 2 3 6 4 1
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

# Sample Output:

0 4 5

# 解释

第一行给定节点数和边数，之后每一行表示一条边的起点和终点，然后给定测试数以及每行一组节点编号的随机排列。输出不是拓扑排序的测试组号。

# 一种思路

验证拓扑很简单，只需要看节点在被列举到的时候入度是不是为 0 就行。所以可以在构建边的时候创建好入度数组，并记录某个节点有哪些指向的节点。当遍历读到一个节点时把它指向的所有节点入度 - 1 即可。

# 解答

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int N, M, K;
int in[MAX], tmpin[MAX];
set<int> edge[MAX];
int main()
{
    cin >> N >> M;
    int from, to;
    for (int i = 0; i < M; i++)
    {
        cin >> from >> to;
        in[to]++;
        edge[from].insert(to);
    }
    cin >> K;
    int num;
    bool space = false;
    for (int i = 0; i < K; i++)
    {
        bool istopo = true;
        memcpy(tmpin, in, sizeof(in));
        for (int j = 0; j < N; j++)
        {
            cin >> num;
            if (tmpin[num] != 0){
                istopo = false;
            }
            if (istopo){
                for (auto k: edge[num]){
                    tmpin[k]--;
                }
            }
        }
        if (!istopo){
            if (space){
                cout << " ";
            }
            cout << i;
            space = true;
        }
    }
}