PAT_A1146#Topological Order

Source:

PAT A1146 Topological Order (25 分)

Description:

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.

PAT_A1146#Topological Order

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
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

Keys:

Attention:

  • 性质:若图顶点按照拓扑排序重新编号,则存储矩阵为上三角阵;
  • 由性质可以推断出,若存储图的矩阵为三角阵,则存在拓扑排序,反之不一定成立;
  • 拓扑排序算法本身比较简单,了解概念之后自然就可以写出了~

Code:

 1 /*
 2 Data: 2019-05-19 20:41:28
 3 Problem: PAT_A1146#Topological Order
 4 AC: 22:04
 5 
 6 题目大意:
 7 判别拓扑排序
 8 输入:
 9 第一行给出顶点数N<=1e3,和边数M<=1e4
10 接下来M行,给出顶点及其有向边(顶点从1~N)
11 接下来给出查询次数K
12 接下来K行给出顶点序列
13 输出:
14 按序号给出不是拓扑排序的序列(0~K-1)
15 */
16 
17 #include<cstdio>
18 #include<algorithm>
19 #include<vector>
20 using namespace std;
21 const int M=1e3+10;
22 vector<int> grap[M],id(M),ans;
23 
24 int main()
25 {
26 #ifdef    ONLINE_JUDGE
27 #else
28     freopen("Test.txt", "r", stdin);
29 #endif
30 
31     int n,m,u,v,s[M];
32     scanf("%d%d", &n,&m);
33     fill(id.begin(),id.end(),0);
34     for(int i=0; i<m; i++)
35     {
36         scanf("%d%d",&v,&u);
37         grap[v].push_back(u);
38         id[u]++;
39     }
40     scanf("%d", &m);
41     for(int i=0; i<m; i++)
42     {
43         vector<int> d = id;
44         for(int j=0; j<n; j++)
45             scanf("%d", &s[j]);
46         for(int j=0; j<n; j++)
47         {
48             v=s[j];
49             if(d[v]==0)
50                 for(int k=0; k<grap[v].size(); k++)
51                     d[grap[v][k]]--;
52             else
53             {
54                 ans.push_back(i);
55                 break;
56             }
57         }
58     }
59     for(int i=0; i<ans.size(); i++)
60         printf("%d%c", ans[i],i==ans.size()-1?'\n':' ');
61 
62     return 0;
63 }

 

上一篇:并查集判断几个环


下一篇:PAT 1142 Maximal Clique