codeforces 510 C. Fox And Names
http://codeforces.com/contest/510/problem/C
题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。
思路：将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串，从前往后扫，直到不相等的那一位，设为k,然后连边，指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串，那么不影响。如果后者是前者的字串，则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序（标准的）最小的方案。所以存点的时候用优先队列存。
/* ***********************************************
Author :111qqz
Created Time :2015年12月06日 星期日 15时16分50秒
File Name :code/cf/problem/510C.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
7int n;
8char st[N][N];
9int p[30];
10int offset[30];
11bool conc[30][30];
12int in[N];
13int ans[N];
14struct node
15{
16 int x;
17 node(int xx)
18 {
19 x=xx;
20 }
21 bool operator <(const node a)const{
22 return x>a.x;
23 }
24};
25bool getconc( int x,int y)
26{
27 int lx = strlen(st[x]);
28 int ly = strlen(st[y]);
29 int len = min(lx,ly);
30 for ( int i = 0; i < len ; i++)
31 {
32 if (st[x][i]!=st[y][i])
33 {
34 conc[st[x][i]-'a'][st[y][i]-'a'] = true;
35 return true;
36 }
37 }
38 // if (lx>ly) return false;
39 return true;
40}
41bool pre()
42{
43 ms(conc,false);
44 ms(in,0);
45 scanf("%d",&n);
46 for ( int i = 0 ;i < n ; i++) scanf("%s",st[i]);
1 bool ok = true;
2 for ( int i = 0 ; i < n-1 ; i++)
3 {
4 ok = getconc(i,i+1);
5 if (!ok) break;
6 }
7 if (ok) return true;
8 return false;
9}
1bool topo()
2{
3 priority_queue<node>q;
4 for ( int i = 0 ; i < 26 ; i++)
5 if (in[i]==0) q.push(i);
int cnt = 0 ;
1 while (!q.empty())
2 {
3 node v = q.top();q.pop();
4 cnt++;
5 ans[cnt]=v.x;
6 for ( int i = 0 ; i < 26 ; i++)
7 {
8 if (!conc[v.x][i]) continue;
9 in[i]--;
10 if (in[i]==0) q.push(i);
11 }
12 }
13 if (cnt<26) return false;
14 return true;
15}
16int main()
17{
18 #ifndef ONLINE_JUDGE
19 freopen("code/in.txt","r",stdin);
20 #endif
21 if (pre())
22 {
23 for ( int i = 0 ; i < 26 ; i++)
24 for ( int j = 0 ; j < 26 ; j++)
25 if (conc[i][j]) in[j]++;
26 if (topo())
27 {
28 for (int i = 1 ; i <= 26 ; i++)
29 printf("%c",char(ans[i]+'a'));
30 puts("");
31 }
32 else
33 {
34 puts("Impossible");
35 }
36 }
37 else
38 {
39 puts("Impossible");
40 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}