PAT_1146

1146 Topological Order

题目描述

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.

gre.jpg

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
3 4

思路

要求判断给出的每一个序列是否符合拓扑序列 ,要解决这个问题首先要知道拓扑排序怎么计算

拓扑排序首先我们将有向图的每一个节点的入度计算出来,找出入度为0的节点,表示没有节点必须要出现在它前面(即可以将此节点作为下一个输出的节点,这里我们就可以得到拓扑排序的答案不是唯一的),并且将以此节点指向的节点的入度进行-1,依次向下判断则得出拓扑排序

现在我们将上诉过程变更为判断性的即可

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e3+10;
typedef long long ll;
int n,m,k,_in[maxn],order[maxn];
vector<int> edge[maxn],ans;

bool Judge()
{
int tmp[maxn];
for(int i =1 ;i <= n;i ++)
tmp[i] = _in[i];
for(int i =1 ;i <= n;i ++)
{
if(tmp[order[i]] != 0)
return false;
else
{
for(int j = 0;j < edge[order[i]].size();j ++)
tmp[edge[order[i]][j]] --;
}
}
return true;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i =0 ;i < m;i ++)
{
scanf("%d%d",&x,&y);
_in[y] ++;
edge[x].push_back(y);
}
scanf("%d",&k);
for(int i =0 ;i < k;i ++)
{
for(int j =1 ;j <= n;j ++)
scanf("%d",order+j);
if(!Judge())
ans.push_back(i);
}

for(int i =0 ;i < ans.size();i ++)
printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');

return 0;
}
-------------本文结束感谢您的阅读-------------
显示 Gitment 评论