Number of Connected Components in an Undirected Graph - Union Find - Leetcode 323 - Python

0:00 - Read the problem
4:36 - Drawing Explanation
11:00 - Coding Explanation

leetcode 323

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

[halahmilksheikh]

Union Find is a cool algorithm but the DFS is so much less code, so less chances of errors and typos. It applies to way more problems too. I was doing number of provinces and the code was way more complicated with union find

[ChanChan-pgwu]

I learnt about UnionFind from this video. A word that means nothing to me 2 months ago! Thank you for the excellent explanation. You are much better at teaching than my college professors.

[pabloj]

Some Thoughts:
Use Union-Find when you have a large, sparse graph and need efficient connectivity checks and merges. It is especially suitable for dynamic graph problems where the structure of the graph changes frequently.

Use DFS when you need to traverse the graph, find paths, or need more information about the graph's structure. It is also a good choice for dense graphs and for problems where readability and simplicity are more important.

[Jay-eebo]

Just wanted to say thank you for these videos man. I've been putting off the leetcode grind for a couple of years now and your videos are the clearest on youtube by far and are making learning a breeze! :)

[pabloj]

I find using DFS, VisitedSet and a Counter to be a much more natural way to solve this to me. This is how i approached it below. But it is good to know Union Find algorithm too in case it ever comes in handy.

# Create an adjacency list to represent the graph
graph = {i: [] for i in range(n)}
for edge in edges:



# A set to keep track of visited nodes
visited = set()

def dfs(node: int):
# Mark the node as visited
visited.add(node)
# Visit all the neighbors
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)

# Counter for the number of connected components
components = 0

# Iterate through all nodes
for i in range(n):
if i not in visited:
# If a node hasn't been visited, it's a new component
dfs(i)
components += 1

return components

[saswataacharya]

LC 684 - Redundant Connection is another Union Find Problem on Leetcode; pretty similar to this one.Thanks for clarifying this concept

[dvsvkimo]

This is super awesome! I have been using BFS or DFS traversal for pretty much all work-related graph problems so far. I have learned something new today!

[venkatasundararaman]

My initial thought was to pass the parent array to a set and return the length of it. This way I thought we can get all the unique parents and it will match the number of connected components, But your trick to decrement the n on each union is very nice.

[alantian.channel]

Amazing video with detailed concept illustration!
I found a recursion could be used in find function.
def find(n1):
# find the parent of n1
if n1 == par[n1]:
return n1
# path compression
par[n1] = par[par[n1]]
return find(par[n1])

[atishaytiwari]

You don't have to update the rank of p2 when (rank[p2] > rank[p1]) because we are only adding one node at a time, so the length of (root p2 node) is either gonna stay less than it's rank or become equal to the rank.

[doritoflake]

NIce video - I think the key takeaway for the complexity analysis is that this algo would be running in O(E * V) Time (where V is no of node aka N) if implemented without that par[res] == par[par[res]] line. Since you added that optimization the traversal of the nodes is cut by half leading to a O(E * log(V)) Time which is why Union Find is more optimal. :)

[daniel.w]

I think we should only change the rank when they are equal and increment it by one, because all the other cases we can still make a tree of max rank by joining to the root of the biggest tree. but if the ranks are equal the biggest tree height is going to increase by one because we are adding an edge.

[sitianlu]

Why we need the while loop in the find function? I thought we are always setting the ultimate parent in parent array. For example, in drawing explanation, after union 2, we set par[2] to 0, not 1

[chandrikasaha]

Love all your videos. God knows when i too can think and write codes as fast

[arashbarmas]

Thank you Neetcode!

I don't see why you are using the rank array because it doesn't really matter; once we see that their parents aren't the same we can connect them. I posted my code below as a reference.



class Solution(object):
def countComponents(self, n, edges):
par = [i for i in range(n)]

def find(n):
if n == par[n]:
return n
return find(par[n])

count = n
for n1, n2 in edges:
p1 = find(n1)
p2 = find(n2)

if p1 == p2:
continue
else:
par[p2] = p1
count -= 1
return count

[akanksha]

How can you make everything daunting so easy? Hats off to you sir.

[Gerald-izmv]

whats the advantage of union find vs dfs?

[CharlesGreenberg]

Why not just update the parent once, at the end of the while loop? Since you’re doing this every time, the max rank should always be 2 anyway.

[vibhorsharma]

DFS solution that remains consistent throughout all problems:

class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
res=0
visit=set()
graph = {i:[] for i in range(n)}
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)


def dfs(i):
if i in visit:
return False
if i in cycle:
return True

cycle.add(i)
T=1
for j in graph[i]:
T = T and dfs(j)
return T

for i in range(n):
cycle=set()
if dfs(i):
res+=1
visit.update(cycle)

return res

[servantofthelord]

Aghhh, this was so elegant! Thank you!