题解：AT_icpc2012autumn_a Dictionary

题意

给定

n

个字符串，判断是否有一种字典序使得它们按这种字典序排序。当

s

为

t

的前缀时，

s

应当排在

t

前面。

解法

如果

s \le t

，要么

s

是

t

的前缀，或者有一个最小的

i

，使得

s_i < t_i

。
用图论解决这个问题。
找到这个

i

，

s_i

向

t_i

连一条边。由此构成一个有向图，

u

到

v

有边代表

u<v

。显然的，如果图中有环，那么环里的字母都大于且小于彼此，这样是无解的。

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

CPP

#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;
}

题解：AT_icpc2012autumn_a Dictionary

文章操作

题意

解法

相关推荐

评论

题解：AT_icpc2012autumn_a Dictionary