BinarySearch.io Direct Closure

January 14, 2021

Problem Statement

Given a two-dimensional list of integers graph representing an undirected graph as an adjacency list, return a two-dimensional matrix M where

M[i][j] = 1 if there is a path between vertices i and j. M[i][j] = 0 otherwise. Constraints

1 ≤ n * m ≤ 100,000 where n and m are the number of rows and columns in graph

Problem Link

Intuition

We use union-find data-structure with path compression to solve this.

For every edge perform union operation between the nodes

To see if nodes are connected perform find operation

Implementation

We implement a unionfind class with path compression. For every edge (u,v) in the graph do uf.union(u, v)

To generate the matrix iterate over the whole matrix with pointers i and j and check uf.connected(i, j)

Time Complexity

O(n^2) considering amortized constant time for union and find operation

Space Complexity

O(n) is the additional space required for union find datastructure

Code

class UnionFind:
    def __init__(self, N):
        self._parents = [i for i in range(N)]
        self._n = N

    def find(self, p: int):
        root = p
        while root != self._parents[root]:
            root = self._parents[root]
        true_root = root
        while p != true_root:
            temp = self._parents[p]
            self._parents[p] = true_root
            p = temp
        return root

    def connected(self, p: int, q: int):
        return 1 if self.find(p) == self.find(q) else 0

    def union(self, p: int, q: int):
        root_p, root_q = self.find(p), self.find(q)
        if root_p == root_q:
            return
        root = p
        while root != self._parents[root]:
            root = self._parents[root]

        self._parents[root] = root_q


class Solution:
    def solve(self, graph):
        N = len(graph)
        uf = UnionFind(N)
        matrix = [[0] * len(graph) for i in range(N)]
        for i, nodes in enumerate(graph):
            for node in nodes:
                uf.union(i, node)
        for i in range(N):
            for j in range(N):
                matrix[i][j] = uf.connected(i, j)

        return matrix

Written by Ganesh Iyer A software engineer building tools for AI in healthcare. Follow me on twitter