图论 判断是否有环

前言：有点忘记是怎么判断一个图中是否是有环

如果是一个无向图，其实可以直接dfs，加上一个vis数组来一起判断

如果是有向图呢，

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:n = numCoursesed = [[] for _ in range(n)]for x in prerequisites:u,v = xed[v].append(u)cnt = [0]*(n)flag = Falsedef dfs(x):nonlocal flagcnt[x] = 1if flag:returnfor v in ed[x]:if cnt[v] == 0:dfs(v)if cnt[v] == 1:flag = Truereturncnt[x] = 2for i in range(n):if cnt[i] == 0:dfs(i)return not flag