题解 P3065 【[USACO12DEC]第一!First!】
原文在此 https://www.jianshu.com/p/6fb17406b66d[](https://www.jianshu.com/p/6fb17406b66d) 原文有图，luogu不会插图。。。。
因为涉及到字典序的问题，那么应该能想到字典树。很显然字符串s1如果比字符串s2的字典序小的话，只有两种情况，s1是s2的前缀；以及他们有相同的前缀单在相同前缀后面的部分那一部分s1的优先级更大；
所以将所以字符串建成一棵字典树，然后再在字典树上遍历每一串字符串，如果有字符串已经是他的前缀，无论怎么改变26个字母的排列也无济于事，否则判断优先级，及上一段所说的情况二； 判断优先级有个很巧的办法---->
如图手画的十分丑陋不要介意哈
字符串s1 为 mma 字符串s2 为 mmb
现在要使mmb的优先级大于mma的优先级，那如何判断通过26个字母的变换后mmb能否优先于mma呢，应该一眼看出把a，b交换位置后s2的字典序就小于s1了，那么接下来就是要找到一种证明的方法；
他们都有相同的mm前缀，那么要使s2的优先级大，就要使b的优先级大，及相同前缀后面部分的优先级大，跟之前所说的一样。
设计到优先级的问题我们绞尽脑汁后应该能想到一个叫拓扑序的神奇的东西，那么再上一张丑图hh
构造这样的图，此时a，b在拓扑排序后的顺序是在同一层的，所以可以瞎把a，b交换位置都可以，故可以将a，b交换位置使得s2的优先级大于s1；
再来一个反例加深理解
无法构成拓扑序，因为a，b无论怎么交换位置，mmab都在mmba前面
应该很清楚了吧！！
如果还不理解建议自己多画几个，一定要勇于动手！！
下面上代码喽！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct Node{
int son[27],end;
}N[300010];
vector<int> E[27];
int n,cnt=1,ind[30010],ans_sum,used[27][27];
string ans[30010],s[30010];
void insert(string s){
int now=1;
for(int i=0;i<s.length();i++){
if(!N[now].son[s[i]-'a']) N[now].son[s[i]-'a']=++cnt;
now=N[now].son[s[i]-'a'];
}
N[now].end++;
}
int work(string s){
int now=1;
for(int i=0;i<s.length();i++){
int t=s[i]-'a';
if(N[now].end) return 0;
for(int j=0;j<26;j++){
if(N[now].son[j]&&t!=j){
E[t].push_back(j);
ind[j]++;
}
}
now=N[now].son[t];
}
return 1;
}
int check(){
queue<int> q;
for(int i=0;i<26;i++) if(!ind[i]) q.push(i);
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<E[u].size();i++){
ind[E[u][i]]--;
if(!ind[E[u][i]]) q.push(E[u][i]);
}
}
for(int i=0;i<26;i++) if(ind[i]) return 0;
return 1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s[i];
insert(s[i]);//建字典树
}
for(int i=1;i<=n;i++){
memset(used,0,sizeof(used));
memset(ind,0,sizeof(ind));
for(int j=0;j<27;j++) E[j].clear();
if(!work(s[i])) continue;//如果有人是它的前缀返回0，直接不干了，如果没有，顺便建好图，准备接下来拓扑排序
if(check()) ans[++ans_sum]=s[i];//如果符合拓扑序 记录答案
}
printf("%d\n",ans_sum);
for(int i=1;i<=ans_sum;i++) cout<<ans[i]<<endl;
return 0;
}