1146 Topological Order (25分)

题目

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.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers $N(\le1,000)$N(≤1,000), the number of vertices in the graph, and $M(\le10,000)$M(≤10,000), the number of directed edges. Then $M$M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to $N$N. After the graph, there is another positive integer $K(\le100)$K(≤100). Then $K$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
5
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:

3 4

题目大意

题目给出一个拓扑图，然后给出若干个拓扑序列，要求判断哪些拓扑序列是不合法的；

思路

线将有向图存起来，只需要存储某个节点指向的下一节点即可，同时记录每个节点的入度，在判断是否合法时将入度信息复制一个备份，没遍历一个节点，将该节点的下一了节点的入度减一，当当前节点的入度值不为0时，就表示还有前驱节点，那么这个拓扑序列就是不合法的；

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main(){
    int n, m;
    vector<vector<int> > mp;
    vector<int> indegree;
    scanf("%d%d", &n, &m);
    mp.resize(n+1), indegree.resize(n+1);
    fill(indegree.begin(), indegree.end(), 0);
    for(int i=0, v1, v2; i<m; i++){
        scanf("%d%d", &v1, &v2);
        mp[v1].push_back(v2);
        indegree[v2]++;
    }
    int k;
    vector<int> ans, order;
    order.resize(n);
    scanf("%d", &k);
    for(int i=0; i<k; i++){
        vector<int> temp = indegree;
        for(int j=0; j<n; j++){
            scanf("%d", &order[j]);
        }
        bool flag = true;
        for(int j=0; j<n; j++){
            if(temp[order[j]] != 0){
                flag = false;
                break;
            }
            for(int t=0; t<mp[order[j]].size(); t++)
                temp[mp[order[j]][t]]--;
        }
        if(!flag)
            ans.push_back(i);
    }
    for(int i=0; i<ans.size(); i++){
        if(i)
            printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
    return 0;
}