时间限制：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
字符集为小写字符
题目连接：B.假的字符串
比赛的时候没想到拓扑排序，只想到了用前缀排除掉部分不合法的串，但是对于abb,aba,bab,baa这四个串，明显简单的前缀还不够
看了别人的题解才懂拓扑排序的意义，假设当前字符串$S_i$可以成为最小字典序的串，那么它要符合两个条件
- 没有其他串是它的前缀
- 在所有串构成的$Trie$树中$S_i$这条路径上的任意结点$u_i$的优先级要比其所有兄弟结点$v_i$的优先级高。
第二个条件可以发现兄弟结点存在优先级关系，假设当前走到的结点对应字符是$cha$，它的某一个兄弟结点对应字符是$chb$，那么应该从$cha$向$chb$连一条有向边，最后拓扑排序一下看是否存在某种优先级关系使得$S_i$成为字典序最小的串。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
typedef long long LL;
const int N = 30005;
const int M = 300005;
const int ALL = (1 << 26) - 1;
struct Trie
{
int nxt[26], cnt;
void init()
{
for (int i = 0; i < 26; ++i)
nxt[i] = 0;
cnt = 0;
}
} L[M];
int sz;
char s[M];
int st[N], len[N], pos[N];
int E[30][30], deg[30], A[30][30];
void clr()
{
for (register int i = 0; i < 30; ++i)
{
deg[i] = 0;
for (register int j = 0; j < 30; ++j)
E[i][j] = A[i][j] = 0;
}
}
void init()
{
sz = 0;
L[sz++].init();
}
inline int newnode()
{
L[sz].init();
return sz++;
}
inline int check(char s[], int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = s[i] - 'a';
if (L[u].cnt)
return false;
for (register int j = 0; j < 26; ++j)
{
if (v != j && L[u].nxt[j] && !A[v][j])
{
A[v][j] = 1;
E[v][++E[v][0]] = j;
++deg[j];
}
}
u = L[u].nxt[v];
}
return true;
}
inline int topsort()
{
queue<int>Q;
int state = 0;
for (int i = 0; i < 26; ++i)
{
if (!deg[i])
Q.push(i), state |= (1 << i);
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (register int i = 1; i <= E[u][0]; ++i)
{
int v = E[u][i];
if (--deg[v] == 0)
{
Q.push(v);
state |= (1 << v);
}
}
}
return state == ALL;
}
inline void ins(char s[], int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = s[i] - 'a';
if (!L[u].nxt[v])
L[u].nxt[v] = newnode();
u = L[u].nxt[v];
}
L[u].cnt = 1;
}
int main(void)
{
register int n, i, j, ed;
scanf("%d", &n);
init();
for (i = 1; i <= n; ++i)
{
st[i] = st[i - 1] + len[i - 1];
scanf("%s", s + st[i]);
len[i] = strlen(s + st[i]);
ins(s + st[i], len[i]);
}
for (i = 1; i <= n; ++i)
{
clr();
if (check(s + st[i], len[i]) && topsort())
pos[++pos[0]] = i;
}
printf("%d\n", pos[0]);
for (i = 1; i <= pos[0]; ++i)
{
int x = pos[i];
for (ed = st[x] + len[x], j = st[x]; j < ed; ++j)
putchar(s[j]);
puts("");
}
return 0;
}