Graph Valid Tree - Leetcode 261 - Python

0:00 - Read the problem
2:45 - Drawing Explanation
10:06 - Coding Explanation

leetcode 261

#graph #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[lasbutious]

This was indirectly the best video explaining how to find a loop in an undirected graph

[yashsrivastava]

With your kind of explanation skills, I wish someday you create videos on System Design preparation videos.

[dpynsnyl]

Another use case of union find. In love with the algorithm!!

[tarastsugrii]

It's possible to solve this problem using basic tree properties - it's connected and has |V|-1 edges, so doing a single traversal to check if graph is connected combined with check that len(edges) == n - 1 should suffice.

[danielsun]

Since this problem is focusing on determine there is no cycle or not, so the first idea come up with me is using the Union find algorithm. Also, it can be solved with the normal DFS.
Union-Find Solution:
def valid_tree(self, n: int, edges: list):
if n - 1 != len(edges):
return False

parent = [i for i in range(n)]
rank = [1] * n
def find(n):
p = parent[n]
while p != parent[p]:
parent[p] = parent[parent[p]]
p = parent[p]
return p
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2:
return 0
if rank[p1] > rank[p2]:
parent[p2] = p1
rank[p1] += rank[p2]
else:
parent[p1] = p2
rank[p2] += rank[p1]
return 1
res = n
for n1, n2 in edges:
res -= union(n1, n2)
return res == 1

[servantofthelord]

Another toughie, but rewarding when you figure it out. Thanks!

[subhashreebanik]

Hey there! Firstly, your videos are AMAZING. I love watching your videos whenever I'm stuck. I can't thank you enough for existing Neetcode.
Recently, I've found out that I get stuck on recursive solutions. I don't have much knowledge on recursion. What reading material would you suggest so that I can become a pro on recursion?

[isseihyodou]

You can also, solve this by Union Find Algorithm
Python:
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
par = [i for i in range(n)]
rank = [1]*n
conCom = n
def find(n):
p = par[n]
while p != par[p]:
par[p] = par[par[p]]
p = par[p]
return p
def union(n1, n2):
nonlocal conCom
p1, p2 = find(n1), find(n2)
if p1 == p2:
return False
if rank[p1] > rank[p2]:
par[p2] = p1
rank[p1] += rank[p2]
else:
par[p1] = p2
rank[p2] += rank[p1]
conCom -= 1
return True

for n1, n2 in edges:
if not union(n1, n2):
return False
if conCom != 1:
return False
return True

[sk_]

could also run union-find to check for cycles and then return n - 1 == len(edges) to check for connectedness

[hudsonriverrunner]

Wonderful DFS approach ! My solution is to use BFS without tracking prev. Observation: In BFS, there is NO way we can form a cycle without 2 nodes from the same level. Cycle can only be formed by connecting two nodes in the same level, OR visiting a node more than once in a level (it has >=2 parents from the previous level). Either way, it requires two nodes from the same level be connected directly (when we have odd number nodes in a cycle) or indirectly (through a common offspring, when we have even number), together with the root we started from, they form a cycle. Another BFS solution thought I first have is to revisit a node from a offspring two levels after. It can be accepted and has the same time complexity. But it is slower, because we have to go at least 2 more levels before realizing we are actually in a cycle, compared to the first solution. Correct me if I am wrong. Thx guys!

[mahesh_kok]

i tried this problem on directed and my approach didnt worked for undirected and when saw your video my respect for you using prev went through sky ...hats off to you bro

[LavanVivekanandasarma]

Really cool how the problem is a combo of Redundant Connection and Number of Connected Components In An Undirected Graph

[michellewww]

very clear and I could learn DFS in a very logic way. Thanks!!!

[basic--advance]

Additionally it is mentioned in the constrained n is greater than or equal to 1 so we can omit the n==0 check

[bchen]

For anyone that came from Redundant Connection, a little adjustment from that problem's solution can be applied here.

if n == 1: return True
if not edges or len(edges) < (n-1): return False

With the above two lines added, you are good to go.

[aaronhanson]

could we also do a union find algo?
if number of components == 1 and no nodes share the same parent then were good?

[emmanuelromero]

How about Union Find Algo?
# Union Find Algorithm

def Solution():
def graphValidTree(self, n, edges):
parent = [i for i in range(n)]
ranks = [i for i in range(n)]

# Build Find
def find(n1):
p = parent[n1]
while p != parent[p]:
parent[p] = parent[parent[p]] # Path Compression
p = parent[p]
return p

# Build Union
def union(n1, n2):
p1, p2 = find(n1), find(n2)

if p1 == p2:
return False
if ranks[p1] > ranks[p2]:
ranks[p1] += ranks[p2]
parent[p2] = p1
else:
ranks[p2] += ranks[p1]
parent[p1] = p2
return True

for n1, n2 in edges:
if union(n1, n2):
n -= 1
else:
return False
return n == 0

[davidlee]

After solving all NeetCode Graph problems in JavaScript, I just found that JS is not responsive every time to the same technique in DFS. For example: the construction of visit = new Set(); sometimes you have to add value.toString() in order to work out sometimes don't; most of the times you cannot establish this visit array, you just use grid[r][c] to keep track of the visited value. The union find is also problematic, esp. the find() method (sometimes you write p = par[n], sometimes you write p = n in the beginning)and the way you use union(), all variates according to different problems. What a weird and frustrating experience! I found DP easier to implement.

[krishnasharma]

Can we do this by union join to Chek for loop and then checking if parent of each node is root to check for connected components??

[vipinamar]

nodes = set()
no_of_edges = 0
for i in edges:
no_of_edges +=1
nodes.add(i[0])
nodes.add(i[1])
if no_of_edges < len(nodes):
return True
return False