给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树
样例
样例 1:
输入: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
输出: true.
样例 2:
输入: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
输出: false.
注意事项
你可以假设我们不会给出重复的边在边的列表当中. 无向边 [0, 1] 和 [1, 0] 是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。
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):
# write your code here
if len(edges)!=(n-1):
return False
neighbors=collections.defaultdict(list)
for u,v in edges:
neighbors[u].append(v)
neighbors[v].append(u)
visited={}
num_of_visited=1
visited[0]=True
queue=collections.deque()
root=0
queue.append(root)
while queue:
root=queue.popleft()
visited[root]=True
for node in neighbors[root]:
if node not in visited:
visited[node]=True
num_of_visited+=1
queue.append(node)
if num_of_visited==n:
return True
else:
return False
