拓扑排序 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 */