拓扑排序 POJ 1049 Sorting It All Out-白红宇

拓扑排序 POJ 1049 Sorting It All Out

阅读量：7074 次

发布时间：2019-06-28

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

1 /*  2     拓扑排序裸题：有三种情况：  3                     1. 输入时发现与之前的矛盾，Inconsistency  4                     2. 拓扑排序后，没有n个点(先判断cnt，即使一些点没有边连通，也应该是n，此时错误是有环)；  5                         flag = -1 表示不确定；return 2 表示拓扑序唯一  6                     3.     其他情况都是 Sorted sequence cannot be determined.  7   8 */  9 #include 
     
       10 #include 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           14 #include 
          
            15 #include 
           
             16 #include 
            
              17 using namespace std; 18 19 const int MAXN = 30; 20 const int INF = 0x3f3f3f3f; 21 int in[MAXN], ans[MAXN]; 22 vector
             
               G[MAXN]; 23 bool used[MAXN][MAXN]; 24 int n, m; 25 26 int TopoSort(void) 27 { 28 int flag = 0; 29 memset (in, 0, sizeof (in)); 30 for (int i=1; i<=n; ++i) 31 { 32 for (int j=0; j

Q; int cnt = 0; 36 for (int i=1; i<=n; ++i) if (!in[i]) Q.push (i); 37 38 while (!Q.empty ()) 39 { 40 if (Q.size () > 1) flag = -1; 41 int u = Q.front (); Q.pop (); 42 ans[++cnt] = u; 43 for (int i=0; i

转载于:https://www.cnblogs.com/Running-Time/p/4476991.html

你可能感兴趣的文章

python中的str.strip（）的用法

查看>>

递归函数

查看>>