首页 > 代码库 > codeforces Round 290 div1 A
codeforces Round 290 div1 A
传送:http://codeforces.com/problemset/problem/510/C
拓扑排序 一个小trick,字典序不仅要求比较字母大小,还有长度~容易漏掉。。
#include <bits/stdc++.h>using namespace std;vector<int> v[101];queue<int> q;char str[101][101];int in[101];int len[101];int main(){ int n; cin>>n; for(int i=1; i<=n; i++) { scanf("%s", str+i); len[i] = strlen(str[i]); } for(int i=1; i<n; i++) {for(int j=0; j<len[i]; j++) { if(j>=len[i+1]) { printf("Impossible\n"); return 0; } if(str[i][j] == str[i+1][j]) continue; else { v[str[i][j]-‘a‘].push_back(str[i+1][j]-‘a‘); in[str[i+1][j]-‘a‘]++;break; } } } for(int i=0; i<26; i++) if(in[i] == 0) q.push(i); int temp = 0; string res; while(!q.empty()) { int x = q.front(); q.pop(); temp ++; res = res + (char)(x+‘a‘); int size = v[x].size(); for(int i=0; i<size; i++) { in[v[x][i]] --; if(!in[v[x][i]]) q.push(v[x][i]); } } if(temp < 26) printf("Impossible\n"); else cout<<res<<endl; return 0;}
codeforces Round 290 div1 A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。