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.
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.
Example 1:
Input: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true.
Example 2:
Input: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false.
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def validTree(self, n, edges):
# corner case
## empty graph
if len(edges) == 0:
if n == 1:
return True
else:
return False
# test number of edges
if n != len(edges) + 1:
return False
# test fully connected
## build graph
graph = dict()
### build nodes
for e in edges:
graph[e[0]] = set()
graph[e[1]] = set()
### build edges
for e in edges:
graph[e[0]].add(e[1])
graph[e[1]].add(e[0])
## init bsf by putting first node in the queue
queue = collections.deque([edges[0][0]])
queued = set(queue)
## BFS loop
while queue:
# current node
node = queue.popleft()
# add next level nodes if never queued
for nei in graph[node]:
if nei not in queued:
queue.append(nei)
queued.add(nei)
if len(queued) != n: # if didn't queued all nodes
return False
return True
queued记录访问与否的set应当作为是否可以放入queue的提前审查。所以其动作应当与queue同步。
special care