# Path: pyalgs/algorithms/graphs/topological_sort.py
# class DepthFirstOrder(object):
# 
#     marked = None
#     reversePostOrder = None
# 
#     def __init__(self, G):
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digraph()
# 
#         self.reversePostOrder = Stack.create()
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
# 
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
#         self.reversePostOrder.push(v)
# 
#     def postOrder(self):
#         return self.reversePostOrder.iterate()
# 
# Path: pyalgs/data_structures/graphs/graph.py
# class EdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.either()
#         w = edge.other(v)
#         self.adjList[v].add(edge)
#         self.adjList[w].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 if e.either() == v:
#                     yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_edge_weighted_digraph(self):
#         g = DirectedEdgeWeightedGraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e)
#             g.add_edge(e.reverse())
#         return g
# 
# class Digraph(object):
#     V = 0
#     adjList = None
# 
#     def __init__(self, V):
#         self.V = V
#         self.adjList = [None] * V
#         for v in range(V):
#             self.adjList[v] = Bag()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def add_edge(self, v, w):
#         self.adjList[v].add(w)
# 
#     def reverse(self):
#         g = Digraph(self.V)
#         for v in range(self.V):
#             for w in self.adjList[v].iterate():
#                 g.add_edge(w, v)
# 
#         return g
# 
# class DirectedEdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.start()
#         self.adjList[v].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_digraph(self):
#         g = Digraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
# 
#         return g


from abc import ABCMeta, abstractmethod
from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph, Digraph, DirectedEdgeWeightedGraph
        self.marked = [False] * vertex_count
        self._id = [-1] * vertex_count
        for v in range(vertex_count):
            if not self.marked[v]:
                self.dfs(G, v)
                self._count += 1

    def dfs(self, G, v):
        self.marked[v] = True
        self._id[v] = self._count
        for w in G.adj(v):
            if not self.marked[w]:
                self.dfs(G, w)

    def connected(self, v, w):
        return self._id[v] == self._id[w]

    def count(self):
        return self._count

    def id(self, v):
        return self._id[v]


class StronglyConnectedComponents(object):
    marked = None
    _id = None
    _count = 0

    def __init__(self, G):

# Path: pyalgs/algorithms/graphs/topological_sort.py
# class DepthFirstOrder(object):
# 
#     marked = None
#     reversePostOrder = None
# 
#     def __init__(self, G):
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digraph()
# 
#         self.reversePostOrder = Stack.create()
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
# 
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
#         self.reversePostOrder.push(v)
# 
#     def postOrder(self):
#         return self.reversePostOrder.iterate()
# 
# Path: pyalgs/data_structures/graphs/graph.py
# class EdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.either()
#         w = edge.other(v)
#         self.adjList[v].add(edge)
#         self.adjList[w].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 if e.either() == v:
#                     yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_edge_weighted_digraph(self):
#         g = DirectedEdgeWeightedGraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e)
#             g.add_edge(e.reverse())
#         return g
# 
# class Digraph(object):
#     V = 0
#     adjList = None
# 
#     def __init__(self, V):
#         self.V = V
#         self.adjList = [None] * V
#         for v in range(V):
#             self.adjList[v] = Bag()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def add_edge(self, v, w):
#         self.adjList[v].add(w)
# 
#     def reverse(self):
#         g = Digraph(self.V)
#         for v in range(self.V):
#             for w in self.adjList[v].iterate():
#                 g.add_edge(w, v)
# 
#         return g
# 
# class DirectedEdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.start()
#         self.adjList[v].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_digraph(self):
#         g = Digraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
# 
#         return g


# Path: pyalgs/algorithms/graphs/connectivity.py
from abc import ABCMeta, abstractmethod
from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph, Digraph, DirectedEdgeWeightedGraph

        self.marked = [False] * vertex_count
        self._id = [-1] * vertex_count
        for v in range(vertex_count):
            if not self.marked[v]:
                self.dfs(G, v)
                self._count += 1

    def dfs(self, G, v):
        self.marked[v] = True
        self._id[v] = self._count
        for w in G.adj(v):
            if not self.marked[w]:
                self.dfs(G, w)

    def connected(self, v, w):
        return self._id[v] == self._id[w]

    def count(self):
        return self._count

    def id(self, v):
        return self._id[v]


class StronglyConnectedComponents(object):
    marked = None
    _id = None
    _count = 0

    def __init__(self, G):

        if isinstance(G, EdgeWeightedGraph):