Implementando el algoritmo de Kosaraju para CFC’s

Estoy tratando de implementar el algoritmo de Kosaraju para encontrar los componentes fuertemente conexos de un grafo dirigido en tiempo lineal. El objetivo es almacenar y mostrar la lista de tamaños de los SCC.

class Graph:
  def __init__(self, edge_list, num_nodes):
    self.graph = edge_list
    self.rev_graph = self.reverse_graph()
    self.num_nodes = num_nodes

    self.traversed_nodes_p1 = []
    self.traversed_nodes_p2 = []

    self.counter = 0
    self.scc_size_list = []

    self.scc_sl()

  def reverse_graph(self):
    r_graph = []
    for e in self.graph:
      tail = e[0]
      head = e[1]
      r_graph.append([head, tail])
    r_graph = sorted(r_graph, key = lambda x: x[0])
    return r_graph

  def dfs_p1(self, starting_node, g, t_nodes): 
    if starting_node not in t_nodes:
      t_nodes.insert(0, starting_node)
    for i in range(len(g)):
      if g[i][0] == starting_node and g[i][1] not in t_nodes:
        self.dfs_p1(g[i][1], g, t_nodes)

  def dfs_loop_p1(self):
    for i in range(1, self.num_nodes + 1):
      self.dfs_p1(i, self.rev_graph, self.traversed_nodes_p1)

  def dfs_p2(self, starting_node, g, t_nodes):
    if starting_node not in t_nodes:
      self.counter += 1
      t_nodes.append(starting_node)
    for i in range(len(g)):
      if g[i][0] == starting_node and g[i][1] not in t_nodes:
        self.dfs_p2(g[i][1], g, t_nodes)

  def dfs_loop_p2(self):
    for i in self.traversed_nodes_p1:
      self.counter = 0
      self.dfs_p2(i, self.graph, self.traversed_nodes_p2)
      if self.counter > 0:
        self.scc_size_list.append(self.counter)

  def scc_sl(self):
    self.dfs_loop_p1()
    self.dfs_loop_p2()

    self.scc_size_list.sort()
    self.scc_size_list.reverse()

Este código produce la salida correcta para grafos más pequeños (por ejemplo, 9 nodos, 15 aristas).

test_edge_list = [[1,2], [1,9], [2,3], [2,8], [3,4], [3,5], [4,5], [6,5], [6,8], [7,6], [7,9], [8,3], [8,7], [9,2], [9,8]]
test = Graph(test_edge_list, 9)
print(test.scc_size_list)

Pero tarda mucho tiempo en funcionar para grafos más grandes. ¿Cómo puedo optimizar esto?