边工作边刷题:70天一遍leetcode: day 78

时间:2023-03-08 16:50:47
边工作边刷题:70天一遍leetcode: day 78

Graph Valid Tree

要点:本身题不难,关键是这题涉及几道关联题目,要清楚之间的差别和关联才能解类似题:isTree就比isCycle多了检查连通性,所以这一系列题从结构上分以下三部分

  • given a graph or edges?有可能给点的编号,然后只给edges,这个最适合用union-find。如果用dfs,那么要先转化成adjacent list表示。这样如果直接给的连通关系的graph,那么dfs就比较直接了
  • isCycle:directed or undirected:dfs过程中,如果不需要连通,那么要dfs外加一层loop。directed要加一个recStack(一般是个set,因为要判断是不是已经在里面):visited但是不在stack里,说明是从其他通路曾经访问的,可以早return,但不表示false。而undirected只需要visited,需要检查的只有visited的neighbor不是parent,那么return false。
  • isTree:directed or undirected:
    • dfs,undirected:由于需要连通的特性,undirected比较简单,不需要外层loop,直接一遍dfs后看还有没有没连通的。
    • dfs,directed:先要找到root(也就是过一遍所有的结点,找到唯一的无入度的点)。然后从这个结点开始做和undirected一样的dfs,看有没有环,以及最后是否遍历了。注意这里比较tricky,因为如果一个结点有2+个入度,那么一定不是树,而只有这种情况才会出现directed graph无环的特殊情况。
    • 而如果用union-find,undirected/directed都类似,就是看最后是不是只有一个root

https://repl.it/Ci3M/1

# Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

# For example:

# Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

# Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

# Hint:

# Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
# According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
# Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges. # Hide Company Tags Google Facebook Zenefits
# Hide Tags Depth-first Search Breadth-first Search Graph Union Find
# Hide Similar Problems (M) Course Schedule (M) Number of Connected Components in an Undirected Graph class Solution(object):
def validTree(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: bool
"""
parents = range(n)
self.count = n
def find(x):
if parents[x]!=x:
parents[x]=find(parents[x]) return parents[x] def union(x,y):
x,y = find(x),find(y)
if x!=y:
parents[x]=y
self.count-=1
return True
return False for e in edges:
if not union(e[0], e[1]):
return False return self.count==1 sol = Solution()
assert sol.validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])==True
assert sol.validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])==False