对于当前节点
cur
的每一个
neighbour
邻居节点：
没被visted过，看
dfs(neighbour)
是否为true，是的话
dfs(cur)
也return true
被visted过，需要check是一个真的cycle还是说只是回头路。不可以走回头路，只能单向行进
if
visited[neighbour] and neighbour != parent
, then cycle found!
def isCyclicUndirectedGraph(graph: List[List[int]], n: int) -> bool:
visited = [False] * n
def isCyclicUntil(cur, parent):
visited[cur] = True
for neighbour in graph[cur]:
if not visited[neighbour]:
if isCyclicUntil(neighbour, cur):
return True
elif parent != neighbour:
return True
return False
for i in range(n):
if not visited[i]:
if isCyclicUntil(i, -1):
return True
return False
union find
先对edge做去重处理，把双向的两个edge变成只剩下一个
遍历所有edge，如果存在一条edge的两端已经connected，就是环
def isCyclicUndirectedGraph(graph: List[List[int]], n: int) -> bool:
uf = UF(n)
edges = set()
for i in range(n):
for nei in graph[i]:
edge = tuple(sorted([i, nei]))
edges.add(edge)
for x, y in edges:
if uf.find(x) == uf.find(y):
return True
uf.union(x, y)
return False
class UF:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y) -> None:
self.parent[self.find(x)] = self.find(y)
Solu 1：DFS + parent nod
照抄dfs + parent node模版
Code 1：
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def buildGraph():
graph = {i: [] for i in range(n)}
for x, y in edges:
graph[x].append(y)
graph[y].append(x)
return graph
def dfs(cur, prev):
visited[cur] = True
for nei in graph[cur]:
if not visited[nei]:
if dfs(nei, cur):
return True
elif nei != prev:
return True
return False
if len(edges) != n - 1:
return False
graph = buildGraph()
visited = [False] * n
if dfs(0, -1):
return False
return all(visited)
Solu 2：union find
照抄union-find模版
Code 2：
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
uf = UF(n)
for x, y in edges:
if uf.find(x) == uf.find(y):
return False
uf.union(x, y)
return True
class UF:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y) -> None:
self.parent[self.find(x)] = self.find(y)
有向图找环
有环的图是无法做“拓扑排序”的
“拓扑排序”通常用来排序具有依赖关系的任务
一个DAG的“拓扑排序”可能有多个
class Solution:
def isCyclicDirectedGraph(self, graph: List[List[int]], n: int) -> bool:
inDeg = [0] * n
for i in range(n):
for j in graph[i]:
inDeg[j] += 1
queue = [i for i in range(n) if inDeg[i] == 0]
count = 0
while queue:
node = queue.pop(0)
count += 1
for nei in graph[node]:
inDeg[nei] -= 1
if inDeg[nei] == 0:
queue.append(nei)
return count == n
Solu：拓扑排序
照抄拓扑排序模版
Code：
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
indeg = [0] * numCourses
graph = [[] for _ in range(numCourses)]
for course, prerequisite in prerequisites:
indeg[course] += 1
graph[prerequisite].append(course)
queue = [i for i in range(numCourses) if indeg[i] == 0]
res = []
while queue:
course = queue.pop(0)
res.append(course)
for neighbor in graph[course]:
indeg[neighbor] -= 1
if indeg[neighbor] == 0:
queue.append(neighbor)
return res if len(res) == numCourses else []
DFS + 双array标记
visited：如果一个node已经被visited过了（被check过了），就没必要再DFS一次了
即：代表是否已被其他节点启动的DFS访问
recStack：当前recursion中，如果再次遇到了已经遇到过的node，那么有环
即：代表是否已被当前节点启动的DFS访问
如果是找一个环哪具体包含哪些节点 or 计算cycle的大小，可以加一个prev[cur] = prevNode来保存每一步怎么走的
def isCyclicDirectedGraph(graph: List[List[int]], n: int) -> bool:
def dfs(cur) -> bool:
if recStack[cur]:
return True
if visited[cur]:
return False
visited[cur] = True
recStack[cur] = True
for next in graph[cur]:
if dfs(next):
return True
recStack[cur] = False
return False
visited = [False] * n
recStack = [False] * n
for i in range(n):
if not visited[i] and dfs(i):
return True
return False
Solu：DFS + 双array
step 1: DFS+双array找最大环
因为size = 2的cycles们可以拼在一桌说，所以要单独记下
step 2: DFS找size = 2的每个cycle中的两个node分别可以延长出的最长path是多少，把他们都拼到一桌上
step 3: res = max{最大环，所有size = 2的cycles及其extended paths的拼接}
Code：
class Solution:
def __init__(self):
self.sizeTwoCycle = []
self.maxCycle = 0
self.favorite = None
def maximumInvitations(self, favorite: List[int]) -> int:
def buildGraph():
beloved = {i: [] for i in range(len(favorite))}
for i, fav in enumerate(favorite):
beloved[fav].append(i)
return beloved
beloved = buildGraph()
self.favorite = favorite
self.countCycle(beloved)
print(self.maxCycle)
return max(self.maxCycle, self.sizeTwoExtend(beloved))
def countCycle(self, beloved) -> None:
def dfs(cur, cycleSize):
if recStack[cur]:
self.maxCycle = max(self.maxCycle, cycleSize)
if cycleSize == 2:
self.sizeTwoCycle.append((cur, self.favorite[cur]))
return
if visited[cur]:
return
visited[cur] = True
recStack[cur] = True
for next in beloved[cur]:
dfs(next, cycleSize + 1)
recStack[cur] = False
visited = [False] * len(beloved)
recStack = [False] * len(beloved)
for i in range(len(beloved)):
if not visited[i]:
dfs(i, 0)
def sizeTwoExtend(self, beloved) -> int:
def dfs(cur) -> int:
if visited[cur]:
return 0
res = 0
for next in beloved[cur]:
res = max(res, dfs(next))
return res + 1
visited = [False] * len(beloved)
res = 0
for i, j in self.sizeTwoCycle:
visited[j] = True
iLongest = dfs(i)
visited[j] = False
visited[i] = True
jLongest = dfs(j)
visited[i] = False
res += iLongest + jLongest
return res
Reference：
