第二组 Hack 出处:<https://www.luogu.com.cn/discuss/575479>
by Moeebius @ 2024-01-09 17:31:40
@[installb](/user/31440)
by Moeebius @ 2024-01-09 17:31:48
@[Moeebius](/user/356003) @[yzy1](/user/207996) 已添加 hack 数据
by installb @ 2024-01-10 13:55:58
dfs 判环其实可以强行令每个点只访问一次(出边指向的点在栈内算找到环),复杂度就是线性的了,正确性也没问题
by KingPowers @ 2024-02-19 11:25:00
@[KingPowers](/user/530180) 请问是这样吗qwq
st是判断当前路径是否有环,Vis是是否访问过,pos是是否有标记
```cpp
void dfs(int u){
if(F)return;
for(int i=0;i<2;i++){
if(pos[tr[u][i]]||vis[tr[u][i]]) continue;
if(st[tr[u][i]]){
F=1;
return;
}
vis[tr[u][i]]=1;
st[tr[u][i]]=1;
dfs(tr[u][i]);
st[tr[u][i]]=0;
}
}
```
但是错了,输出全是NIE,如果删除所有vis是unaccepted100(第一个hack TLE)
by Kniqht @ 2024-02-22 10:32:15
@[Kniqht](/user/315205) 给你参考下我的代码吧,del 是 AC 自动机上不合法的点
```cpp
void dfs2(int now){
ins[now] = vis[now] = true;
For(i, 0, 1){
int to = ch[now][i];
if(del[to]) continue;
if(ins[to]) flag = true;
else if(!vis[to]) dfs2(to);
}
ins[now] = false;
}
```
by KingPowers @ 2024-02-22 10:58:01