传送门:cf 510D
给定n个字符串，问能否存在这样的字母表，使得字符串的排序满足字典序。即依据新的字母表，排序满足字典序大小。
假设满足字典序，则我们可以依据已有的字符串得出各字母之间的大小关系，然后通过拓扑排序来判断是否存在可行解，输出任意解，因此只需要判断是否存在解即可。
/******************************************************
* File Name: a.cpp
* Author: kojimai
* Create Time: 2015年02月03日 星期二 00时32分13秒
******************************************************/
#include
#include
#include
#include
#include
#include
using namespace std; #define FFF 105 char s[FFF][FFF],ans[30]; int in[FFF]; bool link[26][26]; queue
p; bool solve() { // 通过拓扑排序判定是否存在可行解 int cnt = 0; for(int i = 0;i < 26;i++) { if(in[i] == 0) { p.push(i); ans[cnt++] = 'a' + i; } } while(!p.empty()) { int now = p.front(); p.pop(); for(int i = 0;i < 26;i++) { if(link[now][i]) { in[i]--; if(in[i] == 0) { p.push(i); ans[cnt++] = 'a' + i; } } } } ans[26] = '\0'; if(cnt < 26) return false; else return true; } int main() { int n; cin >> n; for(int i = 0;i < n;i++) cin >> s[i]; bool flag = true; memset(link,false,sizeof(link)); memset(in,0,sizeof(in)); for(int i = 0;i < n - 1 && flag;i++) { bool ok = false; int l1 = strlen(s[i]),l2 = strlen(s[i+1]); for(int j = 0;j < l1 && j < l2 && !ok;j++) { if(s[i][j] != s[i+1][j]) { //同一位置的字母不同，则字典序的大小可以比较出来了，即对应字母的相对大小可知 ok = true; if(!link[s[i][j]-'a'][s[i+1][j]-'a']) { in[s[i+1][j]-'a']++; link[s[i][j]-'a'][s[i+1][j]-'a'] = true; } } } if(!ok && l1 > l2) flag = false;//某两个字符串前缀完全相同，但是第一个字符串长度较大，则两字符串必定不满足字典序 } if(!flag) { printf("Impossible\n"); } else { flag = solve(); if(!flag) printf("Impossible\n"); else printf("%s",ans); } return 0; }