graph_valid_tree
1from collections import defaultdict, deque 2 3 4# @leet start 5class Solution: 6 def validTree(self, n: int, edges: list[list[int]]) -> bool: 7 """ 8 A graph is a tree if it has n - 1 edges 9 And a graph is a valid tree if you can visit every node and there's no 10 simple cycles. 11 """ 12 if len(edges) != n - 1: 13 return False 14 15 adj_list = defaultdict(list) 16 for A, B in edges: 17 adj_list[A].append(B) 18 adj_list[B].append(A) 19 20 q = deque([0]) 21 22 visited = {0} 23 24 while q: 25 node = q.popleft() 26 for neighbor in adj_list[node]: 27 if neighbor in visited: 28 continue 29 visited.add(neighbor) 30 q.append(neighbor) 31 32 return len(visited) == n 33 34 35# @leet end 36q = Solution().validTree 37 38 39def test(): 40 assert q(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) 41 assert not q(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])
class
Solution:
6class Solution: 7 def validTree(self, n: int, edges: list[list[int]]) -> bool: 8 """ 9 A graph is a tree if it has n - 1 edges 10 And a graph is a valid tree if you can visit every node and there's no 11 simple cycles. 12 """ 13 if len(edges) != n - 1: 14 return False 15 16 adj_list = defaultdict(list) 17 for A, B in edges: 18 adj_list[A].append(B) 19 adj_list[B].append(A) 20 21 q = deque([0]) 22 23 visited = {0} 24 25 while q: 26 node = q.popleft() 27 for neighbor in adj_list[node]: 28 if neighbor in visited: 29 continue 30 visited.add(neighbor) 31 q.append(neighbor) 32 33 return len(visited) == n
def
validTree(self, n: int, edges: list[list[int]]) -> bool:
7 def validTree(self, n: int, edges: list[list[int]]) -> bool: 8 """ 9 A graph is a tree if it has n - 1 edges 10 And a graph is a valid tree if you can visit every node and there's no 11 simple cycles. 12 """ 13 if len(edges) != n - 1: 14 return False 15 16 adj_list = defaultdict(list) 17 for A, B in edges: 18 adj_list[A].append(B) 19 adj_list[B].append(A) 20 21 q = deque([0]) 22 23 visited = {0} 24 25 while q: 26 node = q.popleft() 27 for neighbor in adj_list[node]: 28 if neighbor in visited: 29 continue 30 visited.add(neighbor) 31 q.append(neighbor) 32 33 return len(visited) == n
A graph is a tree if it has n - 1 edges And a graph is a valid tree if you can visit every node and there's no simple cycles.
def
q(n: int, edges: list[list[int]]) -> bool:
7 def validTree(self, n: int, edges: list[list[int]]) -> bool: 8 """ 9 A graph is a tree if it has n - 1 edges 10 And a graph is a valid tree if you can visit every node and there's no 11 simple cycles. 12 """ 13 if len(edges) != n - 1: 14 return False 15 16 adj_list = defaultdict(list) 17 for A, B in edges: 18 adj_list[A].append(B) 19 adj_list[B].append(A) 20 21 q = deque([0]) 22 23 visited = {0} 24 25 while q: 26 node = q.popleft() 27 for neighbor in adj_list[node]: 28 if neighbor in visited: 29 continue 30 visited.add(neighbor) 31 q.append(neighbor) 32 33 return len(visited) == n
A graph is a tree if it has n - 1 edges And a graph is a valid tree if you can visit every node and there's no simple cycles.
def
test():