codeforces 510c （拓扑排序）-白红宇

codeforces 510c （拓扑排序）

阅读量：4564 次

发布时间：2019-06-08

本文共 2835 字，大约阅读时间需要 9 分钟。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 111111;int topo[205];struct node{    char a[105];}e[105];int n;int g[30][30];int f[30];int main(){    scanf("%d",&n);    int i,j;    for(i = 0; i < n; i++)    {        scanf("%s",e[i].a);    }    memset(f,0,sizeof(f));    memset(g,0,sizeof(g));    for(i = 1; i < n;i++)    {        int l1 = strlen( e[i].a);        int l2 = strlen(e[i-1].a);        for(j = 0; j < l1&& j < l2; j++)        {            if(e[i].a[j] != e[i-1].a[j])            {                int x = e[i].a[j] - 'a';                int y = e[i-1].a[j] - 'a';                if(g[x][y] == 0)                f[y]++;                g[x][y] = 1;                break;            }        }        if(l1 < l2 && j == l1)        {            printf("Impossible\n");            return 0;        }    }    queue
          
            q; for(i = 0; i < 26; i++) { if(f[i] == 0) { q.push(i); } } int cnt = 0; while(!q.empty()) { int w = q.front(); q.pop(); topo[cnt++] = w; for(i = 0; i < 26; i++) { if(g[w][i] == 1) { f[i]--; if(f[i] == 0) q.push(i); } } } if(cnt != 26) { printf("Impossible\n"); return 0; } for(i = cnt-1; i >=0; i--) { printf("%c",topo[i] + 'a'); } printf("\n"); return 0;}

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;char name[120][120];int mat[30][30];int mark[30];int topo[30];int vis[30];int cnt;int main(){    int n;    int i,j,k;    while(scanf("%d",&n)!=EOF)    {        memset(mat,0,sizeof(mat));        memset(mark,0,sizeof(mark));        cnt=0;k=0;        int ok=1;        for(i=1;i<=n;i++)        {            scanf("%s",name[i]);        }        for(i=1;i
         
          len2&&j==len2)            {                ok=0;            }        }        for(i=0;i<26;i++)        {                int flag=-1;                for(j=0;j<26;j++)                {                   if(mark[j]==0)                   {                       topo[k++]=j;                       mark[j]=-1;                       flag=j;                       break;                   }                }                if(flag!=-1)                {                    for(j=0;j<26;j++)                    {                        if(mat[flag][j]==1)                        {                            mark[j]--;                        }                    }                }        }        if(k<26) ok=0;        if(ok)        {            for(i=0;i<26;i++)            {                printf("%c",topo[i]+'a');            }            printf("\n");        }        else printf("Impossible\n");    }    return 0;}