题解：AT_icpc2012autumn_a Dictionary

RioFutaba · 2025-02-18 00:59:11 · 题解

题意

给定 n 个字符串，判断是否有一种字典序使得它们按这种字典序排序。当 s 为 t 的前缀时，s 应当排在 t 前面。

解法

如果 s \le t，要么 s 是 t 的前缀，或者有一个最小的 i，使得 s_i < t_i。
用图论解决这个问题。
找到这个 i，s_i 向 t_i 连一条边。由此构成一个有向图，u 到 v 有边代表 u<v。显然的，如果图中有环，那么环里的字母都大于且小于彼此，这样是无解的。

那么建完图之后暴力枚举从某个字母是否有一条路径能回到它自己，如果有则无解。

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e2+5;
int n,e[26][26];
string a[maxn];
bool is,vis[26];
void fd(int fa,int u,bool o){//o是为了防止刚进去就被判到环
    if(u==fa && o){
        is=1;//找到环了
        return ;
    }
    for(int i=0;i<26;i++)
        if(!vis[i] && e[u][i]) 
            vis[i]=1,fd(fa,i,1);//往前走
}
bool solve(){
    memset(e,0,sizeof(e));
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<n;i++){
        string s=a[i],t=a[i+1];
        bool f=1;
        for(int i=0;i<min((int)s.length(),(int)t.length());i++)
            if(s[i]!=t[i]){
                e[s[i]-'a'][t[i]-'a']=1,f=0;//加边
                break;
            }
        if(f && s.length()>t.length()) return 0;//s不等于t且t是s前缀
    }
    for(int i=0;i<26;i++){
        is=0;
        memset(vis,0,sizeof(vis));
        fd(i,i,0);
        if(is) return 0;
    }
    return 1;
}
int main(){
    while(scanf("%d",&n)){
        if(!n) break;
        if(solve()) puts("yes");
        else puts("no");
    }
    return 0;
}