CodeForces 510C Fox And Names (拓扑排序)

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
string str[110];
vector<int>G[30];
int ind[30];
vector<int>ans;

inline void TopoSort(){
    queue<int>q;    
    for(int i=0;i<26;i++){
        if(!ind[i])q.push(i);
    }
    while(q.size()){
        int u=q.front();q.pop();
        ans.pb(u);
        ind[u]=-1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];    //得到它的子节点
            ind[v]--;
            if(ind[v]==0)q.push(v);
        }
    }
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        cin>>str[i];
    for(int i=2;i<=n;i++){     //枚举字符串
        int len1=str[i-1].size();
        int len2=str[i].size();
        bool fp=false;
        for(int j=0;j<min(len1,len2);j++){
            if(str[i-1][j]!=str[i][j]){     
                int u=str[i-1][j]-‘a‘;
                int v=str[i][j]-‘a‘;
                G[u].pb(v); 
                ind[v]++;        //记录这个点的入度
                fp=true;
                break;            
            }//找到第一个不同的元素
        }        
        if(!fp&&len1>len2)return puts("Impossible"),0; //如果当前串是前一个串的子串
    }
    TopoSort();
    if(ans.size()<26)puts("Impossible");
    else {
        for(int i=0;i<ans.size();i++)
            printf("%c",ans[i]+‘a‘);
        puts("");
    }
}