拓扑排序 POJ 1049 Sorting It All Out

 

  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 <cstdio>
 10 #include <algorithm>
 11 #include <cmath>
 12 #include <iostream>
 13 #include <cstring>
 14 #include <string>
 15 #include <queue>
 16 #include <vector>
 17 using namespace std;
 18 
 19 const int MAXN = 30;
 20 const int INF = 0x3f3f3f3f;
 21 int in[MAXN], ans[MAXN];
 22 vector<int> 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<G[i].size (); ++j)    in[G[i][j]]++;
 33     }
 34     
 35     queue<int> 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<G[u].size (); ++i)
 44         {
 45             int v = G[u][i];
 46             in[v]--;
 47             if (!in[v])    Q.push (v);
 48         }
 49     }
 50 
 51     if (cnt != n)    return 1;
 52     else if (flag == -1)    return -1;
 53     else    return 2;
 54 }
 55 
 56 int main(void)        //POJ 1049 Sorting It All Out
 57 {
 58     //freopen ("POJ_1094.in", "r", stdin);
 59 
 60     char s[5];
 61     while (scanf ("%d%d", &n, &m) == 2)
 62     {
 63         if (n == 0 && m == 0)    break;
 64 
 65         for (int i=1; i<=n; ++i)    G[i].clear ();
 66         memset (used, 0, sizeof (used));
 67 
 68         int flag = 0;
 69         for (int i=1; i<=m; ++i)
 70         {
 71             scanf ("%s", &s);
 72             if (flag)    continue;
 73 
 74             int u = s[0] - A + 1;
 75             int v = s[2] - A + 1;
 76 
 77             if (used[v][u])        {flag = 1;    printf ("Inconsistency found after %d relations.\n", i);    continue;}
 78             
 79             used[u][v] = true;
 80             G[u].push_back (v);
 81 
 82             int res = TopoSort ();
 83             if (res == 1)    {flag = 1;    printf ("Inconsistency found after %d relations.\n", i);    continue;}
 84             else if (res == 2)
 85             {
 86                 flag = 1;
 87                 printf ("Sorted sequence determined after %d relations: ", i);
 88                 for (int i=1; i<=n; ++i)    printf ("%c", ans[i] + A - 1);
 89                 printf (".\n");
 90             }
 91         }
 92 
 93         if (!flag)    puts ("Sorted sequence cannot be determined.");
 94     }
 95 
 96     return 0;
 97 }
 98 
 99 /*
100 Sorted sequence determined after 4 relations: ABCD.
101 Inconsistency found after 2 relations.
102 Sorted sequence cannot be determined.
103 */

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。