codeforces 510c (拓扑排序)
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue> 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<int> 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<cstdio> #include<cstring> #include<iostream> #include<algorithm> 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<n;i++) { if(ok==0) break; int len1=strlen(name[i]); int len2=strlen(name[i+1]); for(j=0;j<len1&&j<len2;j++) { if(name[i][j]!=name[i+1][j]) { int x=name[i][j]-‘a‘; int y=name[i+1][j]-‘a‘; if(mat[x][y]==0) { mat[x][y]=1; mark[y]++; } break; } } if(len1>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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。