题意：给你n个禁止串，然后你只能用字符表的前m个字符去写一个无限长的串，要求是不能包含禁止串，而且串在后面不能出现循环
比赛的时候想的是先建一个自动机，然后将自动机确定化，不能到达的状态全部弄出来。但是对于剩下的状态就卡住了，我怎么才能知道这些状态会构成循环呢？后来看了别人的代码，看到了强连通分量，我就恍然大悟了。其实只需要对剩下的未确定的状态，根据转移边建图，然后跑一次强连通分量。
这么做的效果就是将原图剩下的状态缩成了一个DAG，我们每次只能由根结点往下走，我们必然需要停留在某个强连通分量里，不然的话我走到拓扑序最后的分量就不能再走了（或者说走到拓扑序最后的话，就只能在那个强连通分量沿着分量内的边走“自环”）。如果这个强连通分量是一个环的话，那么显然我们停留在这个强连通分量里的话就会有循环节。所以问题转化为是否存在一个强连通分量它不是一个环。判断方法就是维系一个大小为n的强连通分量至少需要n条边，只要强连通分量内的边大于n，它就不是一个自环。
|
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168 |
#pragma warning(disable:4996)#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <set>#include <vector>#include<queue>#include<stack>#include <cmath>using
namespace std;#define maxn 210000#define ll long longint
n, m;struct
Trie{ Trie *fail, *go[26]; bool
ter; bool
flag; void
init(){ memset(go, 0, sizeof(go)); fail = NULL; ter = false; flag = false; }}pool[maxn], *root;int
tot;void
insert(char
*c){ int
len = strlen(c); Trie *p = root; for
(int i = 0; i < len; i++){ if
(p->go[c[i] - ‘a‘] != 0) p = p->go[c[i] - ‘a‘]; else{ pool[tot].init(); p->go[c[i] - ‘a‘] = &pool[tot++]; p = p->go[c[i] - ‘a‘]; } } p->ter = true;}void
getFail(){ queue<Trie*> que; que.push(root); root->fail = NULL; while
(!que.empty()){ Trie *temp = que.front(); que.pop(); Trie *p = NULL; for
(int i = 0; i < m; i++){ if
(temp->go[i] != NULL){ if
(temp == root) temp->go[i]->fail = root; else{ p = temp->fail; while
(p != NULL){ if
(p->go[i] != NULL){ temp->go[i]->fail = p->go[i]; break; } p = p->fail; } if
(p == NULL) temp->go[i]->fail = root; } que.push(temp->go[i]); } } }}bool
ddfs(Trie *p){ if
(p == root||p==NULL) return
false; if
(p->flag == true) return
p->ter; p->ter |= ddfs(p->fail); p->flag = true; return
p->ter;}int
pre[maxn], low[maxn], sccno[maxn],siz[maxn];int
sta[maxn],st;int
dfs_clock;int
scc_cnt;int
siz2[maxn];void
dfs(int
u){ low[u] = pre[u] = ++dfs_clock; sta[++st] = u; for
(int i = 0; i < m; i++){ Trie *p = pool[u].go[i]; if
(p->ter) continue; int
v = p - pool; if
(!pre[v]){ dfs(v); low[u] = min(low[u], low[v]); } else
if (!sccno[v]){ low[u] = min(low[u], pre[v]); } } if
(low[u] == pre[u]){ ++scc_cnt; while
(1){ int
x = sta[st--]; sccno[x] = scc_cnt; siz[scc_cnt]++; if
(x == u) break; } }}void
find_scc(){ memset(siz, 0, sizeof(siz)); memset(sccno, 0, sizeof(sccno)); memset(low, 0, sizeof(low)); memset(pre, 0, sizeof(pre)); st = dfs_clock = 0; scc_cnt = 0; for
(int i = 0; i < tot; i++){ if
(pool[i].ter) continue; if
(!pre[i]) dfs(i); }}char
str[1500];int
main(){ int
T; cin >> T; while
(T--) { cin >> n >> m; tot = 0; root = &pool[tot++]; root->init(); for
(int i = 0; i < n; i++){ scanf("%s", str); insert(str); } getFail(); for
(int i = 0; i < tot; i++) ddfs(&pool[i]); for
(int i = 0; i < tot; i++){ Trie *p = &pool[i]; for
(int k = 0; k < m; k++){ if
(p->go[k] == NULL){ Trie *temp = p; temp = temp->fail; while
(temp != NULL){ if
(temp->go[k] != NULL) { p->go[k] = temp->go[k]; break; } temp = temp->fail; } if
(temp == NULL) p->go[k] = root; } } } find_scc(); memset(siz2, 0, sizeof(siz2)); for
(int i = 0; i < tot; i++){ if
(pool[i].ter) continue; for
(int j = 0; j < m; j++){ int
k = pool[i].go[j] - pool; if
(sccno[k] == sccno[i]){ siz2[sccno[k]]++; } } } bool
flag = false; for
(int i = 1; i <= scc_cnt; i++){ if
(siz2[i]>siz[i]){ flag = true; break; } } if
(flag) puts("Yes"); else
puts("No"); } return
0;} |
ZOJ3784 String of Infinity(AC自动机&&强连通分量),布布扣,bubuko.com
ZOJ3784 String of Infinity(AC自动机&&强连通分量)
原文：http://www.cnblogs.com/chanme/p/3669777.html