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;
}
全部评论

相关推荐

12-25 16:26
已编辑
河北科技学院 Java
勇敢的牛油不服输:2800-300那不等于2500一个月吗兄弟们
点赞 评论 收藏
分享
程序员花海_:实习和校招简历正确格式应该是教育背景+实习+项目经历+个人评价 其中项目经历注意要体现业务 实习经历里面的业务更是要自圆其说 简历模板尽可能保持干净整洁 不要太花哨的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务