TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- This problem can be solved with DFS as applied in a standard fashion to graphs, but with a small change:
- When creating your adjacency list, if you have for example [0: 1, 2, 3], then nodes 1, 2, and 3 will all be adjacent to 0 as well, but you don’t want to include them since you are checking for cycles that do not include those directly adjacent to node 0.
- Additionally, check in the end whether the number of nodes visited equal the total number of nodes, since otherwise the graph might be disconnected.
- I had first thought that if the node was disconnected
Complexity
Runtime
since we touch each pair of vertices and edges exactly once.
Space
due to axillary space needed for the adjacency list, which stores that many vertices and edges respectively.
Code
from collections import defaultdict
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = set()
dp = {}
def dfs(node, parent):
if node in visited:
return False
if (node, parent) in dp:
return dp[(node, parent)]
visited.add(node)
for v in adj[node]:
if v != parent:
if dfs(v, node) == False:
dp[(node, parent)] = False
return False
dp[(node, parent)] = True
return True
return dfs(0, None) and len(visited) == nNotes
Cards
START Basic Front: Graph Valid Tree Back: Have the previous node in your recursive call so that you avoid having that node called within your adjacency list (i.e. 0 → 1 → 0).
END