Challenge

Given an adjency matrix, find the group of nodes that are connected together.

E.g isConnected = [[1,1,0],[1,1,0],[0,0,1]] Will return 2

Data Structure

Creating a Disjoin Set data structure using a dictionary.

class DisjointSet:

    def __init__(self, n):
        self.rank = {i:i for i in range(n)}

    def __repr__(self):
        return f"Repr:{self.rank}"

    def find(self, val):
        # adding collapsing find
        original_v = val
        while self.rank[val] != val:
            val = self.rank[val]
        if original_v != val:
            self.rank[original_v] = val
        return val
    
    def union(self,val1, val2):
        v1 = self.find(val1)
        v2 = self.find(val2)
        self.rank[v2] = v1

Solution

class Solution:
    
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        ds = DisjointSet(len(isConnected[0]))

        for n, node in enumerate(isConnected):
            for j, v in enumerate(node):
                if v == 1 and j !=n:
                    ds.union(n, j)


        ct = 0
        for k,v in ds.rank.items():
            if k == v:
                ct += 1
        return ct