Daily-Coding-Problem/closure.py at main · quy267/Daily-Coding-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
This problem was asked by Microsoft.

The transitive closure of a graph is a measure of which vertices are reachable from other vertices. It can be represented as a matrix M, where M[i][j] == 1 if there is a path between vertices i and j, and otherwise 0.

For example, suppose we are given the following graph in adjacency list form:

graph = [
    [0, 1, 3],
    [1, 2],
    [2],
    [3]
]
The transitive closure of this graph would be:

[1, 1, 1, 1]
[0, 1, 1, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
Given a graph, find its transitive closure.
"""


def helper(reachable, graph, i, j):
    reachable[i][j] = 1

    for v in graph[j]:
        if reachable[i][v] == 0:
            reachable = helper(reachable, graph, i, v)

    return reachable


def closure(graph):
    n = len(graph)
    reachable = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        reachable = helper(reachable, graph, i, i)

    return reachable


print(closure(graph = [
    [0, 1, 3],
    [1, 2],
    [2],
    [3]
]))