题意描述

[USACO12DEC]First! G

不错的一道题。

给你 \(N\) 个字符串，要求你求出可能的字典序最小的字符串。

对于 可能的最小的字符串，你可以任意排列 \(26\) 个字母，使得其字典序最小。

举个栗子：（好像就是样例）

4 
omm 
moo 
mom 
ommnom 

首先明确一点：当一个单词为另一个单词的前缀时，较长的单词不可能为字典序最小的。

然后发现：

1. 我们可以使用标准字母表使 mom 排在第一个。（即字典序最小）
2. 也可以使用字母表 abcdefghijklonmpqrstuvwxyz 使得 omm 排在第一个。

就是酱紫。

算法分析

字符串让人联想到 \(trie\) 树，优先级关系让人联想到 拓扑排序，于是就解决了。

1. 建立一颗 \(trie\) 树。（有需要的可以看看 ）
2. \(dfs\)，这个...很基础吧。
3. 对于每一个字符串，建立一张有向图，利用 拓扑排序 判断其是否有环，无环就输出。

对于每一个字符串，我们可以设它的字典序是所有字符串中最小的。

也就是说，这个字符串的第 \(i\) 个字母 在 \(trie\) 的第 \(i\) 层（根节点算第 \(0\) 层）的所有字母中 字典序最小。

设这个字符串的第 \(i\) 个字母为 \(u\)，我们可以连单向边 \(u \to v\)，表示我们指定了 \(u\) 的字典序比 \(v\) 小。（其中 \(v\) 是第 \(i\) 层的其它字母）

根据题目描述里的粗体部分，当在遍历时已有字母为单词结尾（即有前缀）可以直接返回 false。

当 \(26\) 个字母间的关系形成环时，也一定不能成为字典序最小的串。

代码实现

#include
#include
#include
#include
#include
#include
#define N 300010
using namespace std;

int n,trie[N][30],tot=1,ru[30],ans=0;
bool sum[N],flag[N],edge[30][30];
string s[N];
queueq;

void insert(string x){
	int p=1;
	for(int i=0;i>s[i];
		insert(s[i]);
	}
	for(int i=1;i<=n;i++){
		if(ask(s[i])){
			ans++;flag[i]=true;
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		if(flag[i]) cout<