题目链接:http://codeforces.com/contest/510/problem/C
题目大意:构造一个字母表,使得按照你的字母表能够满足输入的是按照字典序排下来。
递归建图:竖着切下来,将每个名字的第x个字母从上到下连接建图。然后求拓扑排序。
之所以要拓扑排序,因为要判断在x-1里面有a-->b 在x中有b-->a,这样就形成了一个环。这样一来,就不能够构造字母表了。
【经验教训】:在递归建图的函数中开了两个数组,用来记录字母第一次出现和最后一次出现的位置。。结果就RE在12上。。今后尽量不要在递归函数中开数组。。
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <set>
#include <vector>
#include <iterator>
#include <cstring>
#include <map>
#include <cctype>
#include <iostream>
#include <string>
#include <stdexcept>
using namespace std; int n;
string names[];
bool hasAns = true;
vector<int> G[];
int c[],topo[],t; void solve(int l,int r,int x){
if( l>=r ) return;
if( !hasAns ) return;
for(int i=l;i<=r;i++){
if( x>=names[i].size() ) {
hasAns = false;
return;
}
int j = i+;
for(;j<=r;j++){
if( names[i][x]==names[j][x] ){
continue;
} else {
break;
}
}
while( names[i].size()-<x+&&i<j- ) i++;
solve(i,j-,x+);
i = j-;
} for(int i=l;i<r;i++) {
if( names[i][x]==names[i+][x] ) continue;
G[names[i][x]-'a'].push_back(names[i+][x]-'a');
}
} bool dfs(int u){
c[u] = -;
for(int i=;i<G[u].size();i++){
int v = G[u][i];
if( v< ) continue;
if( c[v]< ) return false;
else if(!c[v] && !dfs(v) ) return false;
}
c[u] = ; topo[--t] = u;
return true;
} bool toposort(){
t = ;
memset(c,,sizeof(c));
for(int u=;u>=;u--) if(!c[u])
if(!dfs(u)) return false;
return true;
} int main(){
cin >> n;
for(int i=;i<n;i++) cin >> names[i];
solve(,n-,);
if( !hasAns ) {
puts("Impossible");
return ;
}
bool hasAns = toposort();
if( !hasAns ) {
puts("Impossible");
return ;
}
for(int i=;i<;i++){
putchar('a'+topo[i]);
}
puts(""); return ;
}