[Neetcode] Number of Connected Components in an Undirected Graph

https://neetcode.io/problems/count-connected-components?list=neetcode150

initial

i immediately knew its union find but i made 2 deadly mistakes

1) IN UNION FIND, I wasnt using finding the parent of the 2 nodes via find_parent function bust just getting the parent of each node via parent[node1]. Thats wrong cuz we are not gonna get the deep root parent

2) After unioning, the parent array is still lazy loaded (path compression). So u HAVE to call find_parent onto each node to truely find the root parent again in ur final logic, not just getting the intermediary parent via parent[node].

3) i was using tmp=-1 and if the find_parent(each node in parent array) is not equal to tmp, i increment answer. But that only works if my parent list is sorted. iF u have [0,0,2,0,2] ur gonna increment wrongly

wrong

int tmp = -1;
for (int par : parent) {
    if (par != tmp) {
        count++;
        tmp = par;
    }
}

sol

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = [i for i in range(n)]

        def find_parent(node):
            if parent[node] != node:
                parent[node] = find_parent(parent[node])
            return parent[node]

        def union(node1, node2):
            par1 = find_parent(node1)
            par2 = find_parent(node2)
            if par1 < par2:
                parent[par2] = par1
            else:
                parent[par1] = par2
        
        check = set()
        for edge in edges:
            e1,e2=edge
            if find_parent(e1)!=find_parent(e2):
                union(e1,e2)
        for p in parent:
            if find_parent(p) not in check:
                check.add(find_parent(p))
        return len(check)

complexity

n + m time where n=nodes number and m=number of edges. This m is cuz in union, each operation is nearly constant thanks to path compression

n space