CF510C Fox And Names——拓扑排序练习

省委代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define maxn 100
#define maxm 10000

using namespace std;

struct edge{
    int next,to;
}e[maxm];

int point[maxn],cnt;
int l,r,q[maxn],in[maxn];
char s[110][110];

void addedge(int x,int y)
{
     e[++cnt].next=point[x];
     e[cnt].to=y;
     point[x]=cnt;
}

void toposort()
{
    l=r=0;
    for(int i=0;i<26;i++)
        if(in[i]==0)
            q[++r]=i;
    while(l<r)
    {
        int x=q[++l];
        for(int i=point[x];i;i=e[i].next)
        {
            int y=e[i].to;
            in[y]--;
            if(in[y]==0)
                q[++r]=y;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]);
    for(int i=1;i<n;i++)
    {
        int len1=strlen(s[i]);
        int len2=strlen(s[i+1]);
        bool flag=0;
        for(int j=0;j<min(len1,len2);j++)
            if(s[i][j]==s[i+1][j])
                continue;
            else
            {
                flag=1;
                in[s[i+1][j]-'a']++;
                addedge(s[i][j]-'a',s[i+1][j]-'a');
                break;
            }
        if(flag==0 && len2<len1)
        {
            printf("Impossible");
            return 0;
        }
    }
    toposort();
    if(l<26)
          printf("Impossible");
    else
        for(int i=1;i<=26;i++)
            printf("%c",q[i]+'a');
    return 0;
}
全部评论

相关推荐

object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务