FilesExpand file tree

master

/

graph-valid-tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (54 loc) · 1.8 KB

master

/

graph-valid-tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (54 loc) · 1.8 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

# 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