https://www.luogu.com.cn/problem/P3065
历史遗留题目，在收藏里吃灰好长时间了，觉得洛谷可以整一个记录加入收藏的时间的功能，让我看看每个题咕了多长时间
然后今天看突然有些会了
给定 (n) 个字符串，可以指定字母之间的大小关系（比如可以指定 (b<a)，其实也就是指定了一种字母表顺序），问哪些串可以在任意一种字母表顺序下字典序最小
trie+建图判环
先把输入的字符串都放到trie上
对于每一个字符串 (s)，设当前考虑到 (s_i)（也就是在trie上走到了 (s_i) 的上一层，要往 (s_i) 走）
那么就假设 (s_i) 是 (s_i) 所在层所有存在的字符中最大的，如何把这个“最大”表达出来？
就拿他向其它字符都连边（单项，大的连向小的），然后直到考虑完 (s_n)，如果连出的图没有环，则说明成立，否则，说明无论什么字母表下，(s) 的字典序都不是最小
至于判环就爱咋判咋判了，我这里用的拓扑排序
还有一点是如果发现某一个字符串是 (s) 的前缀，也说明 (s) 的字典序不可能最小
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
struct tr{
tr *son[26];
int end;
}dizhi[300005],*root=&dizhi[0];
int tot,n;
int map[26][26],in[26];
char *begin[30005];
char s[300005],in_str[300005];
int tail,head,queue[105];
int len[30005],yes[30005];
inline void topo(){
tail=-1;head=0;
for(reg int i=0;i<26;i++)if(!in[i]) queue[++tail]=i;
reg int u,v;
while(head<=tail){
u=queue[head++];
for(v=0;v<26;v++)if(map[u][v])
if(!--in[v]) queue[++tail]=v;
}
}
inline int check(int id,char *s){
tr *now=root;
int num;
std::memset(map,0,sizeof map);std::memset(in,0,sizeof in);
for(reg int i=0;i<len[id];i++){
if(now->end) return 0;
num=s[i]-'a';
for(reg int j=0;j<26;j++)if(now->son[j]&&num!=j&&!map[num][j]){
map[num][j]=1;in[j]++;
}
now=now->son[num];
}
topo();
for(reg int i=0;i<26;i++)if(in[i]) return 0;
return 1;
}
int main(){
n=read();
for(reg int i=1;i<=n;i++){
scanf("%s",in_str);
len[i]=std::strlen(in_str);
tr *now=root;
for(reg int j=0;j<len[i];j++){
if(!now->son[in_str[j]-'a']) now->son[in_str[j]-'a']=&dizhi[++tot];
now=now->son[in_str[j]-'a'];
}
now->end=1;
int tmp=std::strlen(s);
begin[i]=&s[tmp];
for(reg int j=0;j<len[i];j++) s[j+tmp]=in_str[j];
}
int ans=0;
for(reg int i=1;i<=n;i++)if(check(i,begin[i])) yes[i]=1,ans++;
printf("%d
",ans);
for(reg int i=1;i<=n;i++)if(yes[i]){
char *now=begin[i];
for(reg int j=0;j<len[i];j++) putchar(*now),now++;
EN;
}
return 0;
}