CodeForces 510C Fox And Names-蒲公英云

CodeForces 510C Fox And Names

Dear 丶 2022-08-19 08:19 239阅读 0赞

一道拓扑排序题!!

注意判断各种情况，两个字符串比较的时候，从左向右开始比较，当出现不同的字母后，不再向后比较。一个是另一个的前缀，那么长的在后面。

当给出的顺序出现环的时候，或者有串的前缀在串的后面时，出现错误。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
char a[1001][1001];
int in[10001],v[1001][101],cnt;
char b[1001];
using namespace std;
int topsort()
{
    int t1,t2,i,j;
    for(i=0;i<26;i++)
    {
        for(j=0;j<26;j++)
        {
            if(in[j]==0)
            {
                t1=j;
                in[j]=-1;
                break;
            }
        }
        if(j==26)
            return 0;
        b[cnt++]=j+'a';
        for(j=0;j<26;j++)
        {
            if(v[t1][j])
            {
                in[j]--;
            }
        }
    }
    return 1;
} 
int main()
{
    int i,j,m,n,l;
    while(~scanf("%d",&n))
    {
        cnt=0;
        memset(v,0,sizeof(v));
        memset(in,0,sizeof(in));
        for(i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        for(i=0;i<n-1;i++)
        {
            int f=0;
            int l1=strlen(a[i]);
            int l2=strlen(a[i+1]);
            for(j=0;j<min(l1,l2);j++)
            {
                if(a[i][j]!=a[i+1][j])
                {
                    f=1;
                    int t1=a[i][j]-'a';
                    int t2=a[i+1][j]-'a';
                    if(!v[t1][t2])
                    {
                        in[t2]++;
                        v[t1][t2]=1;                        
                    }
                    break;
                }
            }
            if(l2<l1&&f==0)
            {
                printf("Impossible\n");
                return 0;
            }
        }
        if(topsort())        
            puts(b);
        else
            puts("Impossible");
    } 
    return 0;
}