finds the transitive closure of a graph reference https en wikipedia orgwikitransitiveclosureingraphtheory this class represents a directed graph using adjacency lists no of vertices default dictionary to store graph to store transitive closure adds a directed edge to the graph a recursive dfs traversal function that finds all reachable vertices for source mark reachability from source to target as true find all the vertices reachable through target the function to find transitive closure it uses recursive dfsutil call the recursive helper function to print dfs traversal starting from all vertices one by one this class represents a directed graph using adjacency lists no of vertices default dictionary to store graph to store transitive closure adds a directed edge to the graph a recursive dfs traversal function that finds all reachable vertices for source mark reachability from source to target as true find all the vertices reachable through target the function to find transitive closure it uses recursive dfs_util call the recursive helper function to print dfs traversal starting from all vertices one by one
class Graph:
    
    def __init__(self, vertices):
        
        self.vertex_count = vertices

        
        self.graph = {}

        
        self.closure = [[0 for j in range(vertices)] for i in range(vertices)]

    def add_edge(self, source, target):
        
        if source in self.graph:
            self.graph[source].append(target)
        else:
            self.graph[source] = [target]

    def dfs_util(self, source, target):
        

        
        self.closure[source][target] = 1

        
        for adjacent in self.graph[target]:
            if self.closure[source][adjacent] == 0:
                self.dfs_util(source, adjacent)

    def transitive_closure(self):
        

        
        
        for i in range(self.vertex_count):
            self.dfs_util(i, i)

        return self.closure