拓扑排序 Codeforces Round #290 (Div. 2) C. Fox And Names

  1 /*
  2     给出n个字符串，求是否有一个“字典序”使得n个字符串是从小到大排序
  3     拓扑排序
  4     详细解释：http://www.2cto.com/kf/201502/374966.html
  5 */
  6 #include <cstdio>
  7 #include <iostream>
  8 #include <cstring>
  9 #include <string>
 10 #include <map>
 11 #include <algorithm>
 12 #include <vector>
 13 #include <set>
 14 #include <queue>
 15 #include <cmath>
 16 using namespace std;
 17 
 18 const int MAXN = 1e6 + 10;
 19 const int INF = 0x3f3f3f3f;
 20 char s[110][110];
 21 int in[110];
 22 bool lin[27][27];
 23 char ans[27];
 24 
 25 bool TopoSort(void)
 26 {
 27     queue<int> q;
 28     int cnt = 0;
 29     for (int i=1; i<=26; ++i)
 30     {
 31         if (in[i] == 0)
 32         {
 33             q.push (i);
 34             ans[cnt++] = 'a' + i - 1;
 35         }
 36     }
 37     while (!q.empty ())
 38     {
 39         int now = q.front ();   q.pop ();
 40         for (int i=1; i<=26; ++i)
 41         {
 42             if (lin[now][i])
 43             {
 44                 in[i]--;
 45                 if (in[i] == 0)
 46                 {
 47                     q.push (i);
 48                     ans[cnt++] = 'a' + i - 1;
 49                 }
 50             }
 51         }
 52     }
 53     ans[26] = '';
 54     if (cnt < 26)   return false;
 55     else    return true;
 56 }
 57 
 58 int main(void)
 59 {
 60     //freopen ("C.in", "r", stdin);
 61 
 62     int n;
 63     
 64     while (~scanf ("%d", &n))
 65     {
 66         memset (lin, false, sizeof (lin));
 67         memset (in, 0, sizeof (in));
 68         for (int i=1; i<=n; ++i)
 69         {
 70             scanf ("%s", &s[i]);
 71         }
 72         
 73         bool flag = true;
 74         for (int i=1; i<=n-1 && flag; ++i)
 75         {
 76             int len1 = strlen (s[i]);
 77             int len2 = strlen (s[i+1]);
 78             bool ok = false;
 79             for (int j=0; j<=len1-1 && j<=len2-1 && !ok; ++j)
 80             {
 81                 if (s[i][j] != s[i+1][j])
 82                 {
 83                     ok = true;
 84                     if (!lin[s[i][j]-'a'+1][s[i+1][j]-'a'+1])
 85                     {
 86                         in[s[i+1][j]-'a'+1]++;
 87                         lin[s[i][j]-'a'+1][s[i+1][j]-'a'+1] = true;
 88                     }
 89                 }
 90             }
 91             if (!ok && len1 > len2) flag = false;
 92         }
 93         
 94         if (!flag)  puts ("Impossible");
 95         else
 96         {
 97             flag = TopoSort ();
 98             if (!flag)   puts ("Impossible");
 99             else    printf ("%s
", ans);
100         }
101     }
102     
103     return 0;
104 }
编译人生，运行世界！