对于一个有向图判断是否存在环，不只可以使用拓扑排序，直接对整个图 dfs 也可以。但是 dfs 过程中的 vis 数组不能仅设置 "未经过"(0) 与 "已经过"(1) 两种状态，以 "再一次走到 '已经过' 标志" 为基准判环。因为再一次走到某个 "已经过" 状态时，可能是从两条不同的路线走到这一个地方的，并没有形成环（对拓扑来说相当于两条分叉路径汇集到同一个点）。因此，需要额外设置 "当前 dfs 路径已经过"(2) 这种状态。每个点在这三种状态之间切换，具体地：
- 从未经过 \(\rightarrow\) 始终为 \(0\)
- 第一次经过 \(\rightarrow\) 设置为 \(2\)，启动该点的 dfs 过程
- dfs 过程中未找到环，回溯时 \(\rightarrow\) 设置为 \(1\)
对于已经过的点不会再重复搜索，故总复杂度为 \(O(n + m)\)。
例题：ABC456E
code:
def solve():n, m = MII()G = [[] for _ in range(n)]for _ in range(m):u, v = MII()u -= 1v -= 1G[u].append(v)G[v].append(u)W = II()s = [I() for _ in range(n)]# 状态标记：0=未访问，1=在栈中，2=已处理完成vis = [[False] * W for _ in range(n)]@bootstrapdef dfs(u, d):# print(u, d)"""返回是否找到环"""vis[u][d] = 1 # 标记在栈中nd = (d + 1) % W# 检查留在此城市if s[u][nd] == 'o':if vis[u][nd] == 1: # 找到环yield Trueif vis[u][nd] == 0:res = yield dfs(u, nd)if res:yield True# 检查移动到邻居for v in G[u]:if s[v][nd] == 'o':if vis[v][nd] == 1: # 找到环yield Trueif vis[v][nd] == 0:res = yield dfs(v, nd)if res:yield Truevis[u][d] = 2 # 标记为已处理yield False# 从所有 day 1 是假日的城市开始for i in range(n):if s[i][0] == 'o' and vis[i][0] == 0:if dfs(i, 0):print("Yes")returnprint("No")