DFS

class DFS:
    def __init__(self, graph: Graph, source: int):
        self.marked = [False] * graph.v
        self.edge_to = [i for i in range(graph.v)]
        self.source = source
        self.graph = graph
        self.cnt = 0
        self.__validate_v(source)
        self.__dfs(graph, source)

    def __validate_v(self, v):
        if v < 0 or v >= self.graph.v:
            raise Exception("{} illegal".format(v))

    def __dfs(self, graph, v):
        self.marked[v] = True
        self.cnt += 1
        for w in graph.get_adj(v):
            if not self.marked[w]:
                self.edge_to[w] = v
                self.__dfs(graph, w)

    def has_path_to(self, v):
        self.__validate_v(v)
        return self.marked[v]

    def path_to(self, v):
        self.__validate_v(v)
        if not self.has_path_to(v):
            return None
        path = []
        x = v
        while x != self.source:
            path.append(x)
            x = self.edge_to[x]
        path.append(self.source)
        return path

    def count(self):
        return self.cnt

    def connected(self):
        return self.cnt == self.graph.v