PAT 1146 Topological Order[难]-白红宇

PAT 1146 Topological Order[难]

阅读量：6073 次

发布时间：2019-06-20

本文共 1928 字，大约阅读时间需要 6 分钟。

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 (

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 81 21 35 25 42 32 63 46 451 5 2 3 6 45 1 2 6 3 45 1 2 3 6 45 2 1 6 3 41 2 3 4 5 6

Sample Output:

3 4

题目大意：给出一个有向图，并且给定K个序列，判断这个序列是否是拓扑序列。

//我一看见我想的就是，得用邻接表存储图，然后对每一个输入的序列，都进行判断，基本上复杂度是非常高的，就是对每一个序列中的数，判断其之前出现的每一个数是否是它的next，这样来判断，然后写的不对。

#include 
      
       #include
       
        #include
        #include
         
          using namespace std;vector
          
           
            > graph;int main(){ int n,m; cin>>n>>m; graph.resize(n+1); int f,t; for(int i=0;i
            
             >f>>t; graph[f].push_back(t);//因为是单向图 } int u; cin>>u; vector
             
               vt(n); vector
              
                ans; for(int i=0;i
               
                >vt[j]; //检查在其之前出现的是否是在这个图的next里。 bool flag=true; for(int j=1;j

View Code

结果：

//真的很奔溃啊，怎么每个都是不对的，那个2 2 到底是什么意思？我明天再看看吧。

//柳神的代码：

//根据入度出度来判断，非常可以了。。

学习了，要多复习。

转载于:https://www.cnblogs.com/BlueBlueSea/p/9873192.html

你可能感兴趣的文章