LeetCode-Solutions/Python/graph-valid-tree.py at master · pythonpeixun/LeetCode-Solutions · GitHub

History

64 lines (54 loc) · 1.8 KB

Raw

# Time: O(|V| + |E|)

# Space: O(|V| + |E|)

import collections

# BFS solution. Same complexity but faster version.

class Solution(object):

# @param {integer} n

# @param {integer[][]} edges

# @return {boolean}

def validTree(self, n, edges):

if len(edges) != n - 1: # Check number of edges.

return False

# init node's neighbors in dict

neighbors = collections.defaultdict(list)

for u, v in edges:

neighbors[u].append(v)

neighbors[v].append(u)

# BFS to check whether the graph is valid tree.

q = collections.deque([0])

visited = set([0])

while q:

curr = q.popleft()

for node in neighbors[curr]:

if node not in visited:

visited.add(node)

q.append(node)

return len(visited) == n

# Time: O(|V| + |E|)

# Space: O(|V| + |E|)

# BFS solution.

class Solution2(object):

# @param {integer} n

# @param {integer[][]} edges

# @return {boolean}

def validTree(self, n, edges):

# A structure to track each node's [visited_from, neighbors]

visited_from = [-1] * n

neighbors = collections.defaultdict(list)

for u, v in edges:

neighbors[u].append(v)

neighbors[v].append(u)

# BFS to check whether the graph is valid tree.

q = collections.deque([0])

visited = set([0])

while q:

i = q.popleft()

for node in neighbors[i]:

if node != visited_from[i]:

if node in visited:

return False

else:

visited.add(node)

visited_from[node] = i

q.append(node)

return len(visited) == n

LeetCode-Solutions/Python/graph-valid-tree.py at master · pythonpeixun/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

graph-valid-tree.py

Latest commit

History

Breadcrumbs

graph-valid-tree.py

File metadata and controls