【Codeforces Round #290 (Div. 2)-C. Fox And Names】 思维题+拓扑排序

Codeforces Round #290 (Div. 2)-C. Fox And Names

题意

$给你n个字符串，让你设计一种字典序使这n个字符串满足字典序从小到大$
$如果不能设计输出impossible$
$n<=100;|s|<=100$

做法

$n^2扫描所有字符串，对使每两个串字典序不同的主要字母建图（也就是第一个不同的字母）$
$建图之后跑一下拓扑排序，如果满足拓扑序也就是没有环出现，那么直接输出拓扑序即可。$

坑点

$判一下有没有一短一长前缀完全相同，但是长度不同字典序错误的情况。$
$比如AAA，AA，但是AAA出现在前面，这种情况也应该输出impossible$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 105;
char str[maxn][maxn];
vector<int> v[maxn];
int ind[maxn], que[maxn],m;//ind数组要清空
bool topsort()//还要特判自环
{
    int qt = 0;for(int i = 0;i<26; ++i){
    if(ind[i] == 0) que[qt++] = i;}for(int i = 0; i < qt; ++i){
    int u = que[i];for(int j = 0; j < v[u].size(); ++j){
    if(--ind[v[u][j]] == 0) que[qt++] = v[u][j];}}return qt == 26;
}
int main()
{
    int n;int flag=0;//存储是否有前缀完全相同一长一短不满足字典序的情况scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%s",str[i]);for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
    int ff=0;int len1=strlen(str[i]);int len2=strlen(str[j]);for(int pos1=0,pos2=0;pos1<len1&&pos2<len2;pos1++,pos2++){
    if(str[i][pos1]!=str[j][pos2]){
    v[str[i][pos1]-'a'].push_back(str[j][pos2]-'a');ind[str[j][pos2]-'a']++;ff=1;break;}}if(ff==0&&len1>len2) flag=1;}}if(topsort()&&flag==0){
    for(int i=0;i<26;i++) printf("%c",(char)que[i]+'a');}else{
    printf("Impossible\n");}return 0;
}