题目链接：
https://ac.nowcoder.com/acm/problem/15049
题目大意：
给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们
具体思路：
在可以任意定义字符之间的大小关系的前提下，对于当前的字符串，首先满足他的前缀中不存在已经输入的字符串；其次，对于abcd和adcb这种情况，是非法的，如果我们假设b>d,
那么后面就会出现矛盾，这个时候我们可以通过建图判断有没有环来判断这种非法情况。
AC代码：
1 #pragma comment(linker,"/STACK:1024000000,1024000000") 2 #include<bits/stdc++.h> 3 using namespace std; 4 # define ll long long 5 # define inf 0x3f3f3f3f 6 # define lson l,mid,rt<<1 7 # define rson mid+1,r,rt<<1|1 8 const int maxn = 3e5+5; 9 const int N = 3e4+10; 10 int ch[maxn][30]; 11 int val[maxn]; 12 int tot=0; 13 void add_trie(string str){ 14 int len=str.size(); 15 int p=0; 16 for(int i=0;i<len;i++){ 17 int u=str[i]-'a'; 18 if(!ch[p][u])ch[p][u]=++tot; 19 p=ch[p][u]; 20 } 21 val[p]++; 22 } 23 vector<int>Edge[30]; 24 int in[30],vis[30]; 25 void init(){ 26 for(int i=0;i<30;i++){in[i]=0;vis[i]=0;Edge[i].clear();} 27 } 28 bool tuopu(){ 29 queue<int>q; 30 for(int i=0;i<30;i++){ 31 if(!in[i])q.push(i); 32 } 33 while(!q.empty()){ 34 int top=q.front(); 35 q.pop(); 36 vis[top]=1; 37 int len=Edge[top].size(); 38 for(int i=0;i<len;i++){ 39 int to=Edge[top][i]; 40 if(--in[to]==0){ 41 q.push(to); 42 } 43 } 44 } 45 for(int i=0;i<30;i++){ 46 if(!vis[i])return false; 47 } 48 return true; 49 50 } 51 bool judge(string str){ 52 init(); 53 int len=str.size(); 54 int p=0; 55 for(int i=0;i<len;i++){ 56 int u=str[i]-'a'; 57 for(int j=0;j<26;j++){ 58 if(ch[p][j]&&j!=u)Edge[u].push_back(j),in[j]++; 59 } 60 p=ch[p][u]; 61 if(val[p]&&i!=len-1)return false;// 判断当前的字符串的前缀中有没有已经出现过的字符串 62 } 63 if(val[p]>=2)return false;// 判断有没有重复的字符串出现，如果有的话就不满足为字典序最小的字符串了，（好像不判断也能a） 64 return tuopu(); 65 } 66 string str[N]; 67 68 vector<int>ans; 69 int main(){ 70 int T; 71 cin>>T; 72 for(int i=1;i<=T;i++){ 73 cin>>str[i]; 74 add_trie(str[i]); 75 } 76 for(int i=1;i<=T;i++){ 77 if(judge(str[i])){ 78 ans.push_back(i); 79 } 80 } 81 int len=ans.size(); 82 cout<<len<<endl; 83 for(int i=0;i<len;i++){ 84 cout<<str[ans[i]]<<endl; 85 } 86 return 0; 87 }