首页 > 代码库 > codeforces Round 290 div1 A

codeforces Round 290 div1 A

传送:http://codeforces.com/problemset/problem/510/C

 

拓扑排序 一个小trick,字典序不仅要求比较字母大小,还有长度~容易漏掉。。

 

#include <bits/stdc++.h>using namespace std;vector<int> v[101];queue<int> q;char str[101][101];int in[101];int len[101];int main(){    int n;    cin>>n;    for(int i=1; i<=n; i++)    {        scanf("%s", str+i);        len[i] = strlen(str[i]);    }        for(int i=1; i<n; i++)    {for(int j=0; j<len[i]; j++)        {            if(j>=len[i+1])            {                printf("Impossible\n");                return 0;            }            if(str[i][j] == str[i+1][j])                continue;            else            {                v[str[i][j]-a].push_back(str[i+1][j]-a);                in[str[i+1][j]-a]++;break;            }        }    }    for(int i=0; i<26; i++)            if(in[i] == 0)                q.push(i);    int temp = 0;    string res;    while(!q.empty())    {        int x = q.front();        q.pop();        temp ++;        res = res + (char)(x+a);        int size = v[x].size();        for(int i=0; i<size; i++)        {            in[v[x][i]] --;            if(!in[v[x][i]])                q.push(v[x][i]);        }    }    if(temp < 26)        printf("Impossible\n");    else        cout<<res<<endl;    return 0;}

 

codeforces Round 290 div1 A