2021-11-10tri树+拓扑

链接：https://ac.nowcoder.com/acm/problem/15049
来源：牛客网

题号：NC15049
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述

给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们
输入描述:

第一行一个数表示n
之后n行每行一个字符串表示给定的字符串

输出描述:

第一行输出一个数x表示可行的字符串个数
之后输出x行，每行输出一个可行的字符串
输出的顺序和输入的顺序一致

示例1
输入
复制

6
mcfx
ak
ioi
wen
l
a

输出
复制

5
mcfx
ioi
wen
l
a

备注:

对于100%的数据，
n <= 30000 , 字符串总长<= 300000
字符集为小写字符
这道题目大体思路就是两个要点，首先不能最小字符串的前缀不能是其他字符串，第二个是不能出现矛盾的情况（虽然没有第一种情况，但是大小矛盾也不可）这道题目没实现出来，看的别的大佬的博客代码，自己加了更加仔细的注释，我把出处注上：https://www.cnblogs.com/letlifestop/p/10950866.html

#include
using namespace std;
# define ll long long
#define inf 0x3f3f3f3f
# define lson l,mid,rt<<1
# define rson mid+1,r,rt<<1|1
const int maxn = 3e5+5;
const int N = 3e4+10;
int ch[maxn][30];
int val[maxn];
int tot=0;
void add_trie(string str){
int len=str.size();
int p=0;
for(int i=0;iEdge[30];
 int in[30],vis[30];
 void init(){
 for(int i=0;i<30;i++){in[i]=0;vis[i]=0;Edge[i].clear();}
 }
bool tuopu(){//拓扑排序是判断该字符串有没有可能是字典序最小的串 
 //这是形成了儿子之间的所有的先后关系以后，判断有没有环（若出现了环，就说明前后关系出现了悖论，它作为最小子串的可能性破灭） 
 //下面就是老老实实的拓扑判断环 
 queueq;
 for(int i=0;i<30;i++){
 if(!in[i])q.push(i);
 }
 while(!q.empty()){
 int top=q.front();
 q.pop();
 vis[top]=1;
 int len=Edge[top].size();
 for(int i=0;i=2)return false;// 判断有没有重复的字符串出现，如果有的话就不满足为字典序最小的字符串了，（好像不判断也能a）
 return tuopu();
 }
 string str[N];
 vectorans;
 int main(){
 int T;
 cin>>T;
 for(int i=1;i<=T;i++){
 cin>>str[i];
  add_trie(str[i]);
 }
 for(int i=1;i<=T;i++){
 if(judge(str[i])){
 ans.push_back(i);
 }
 }
 int len=ans.size();
 cout<