Обход графика, топологическая сортировка, номер после посещения и номер перед посещением

Question

#Uses python3

import sys

def previsit(v, clock, pre):
    pre[v] = clock
    clock += 1
    return pre
def postvisit(v, clock, post):
    post[v] = clock
    clock += 1
    return post

def reverseg(adj):
    edges = []
    for i in range(len(adj)):
    if adj[i] != []:
        for vertex in adj[i]:
            edges.append([i, vertex])
    edgesr = [[j, i] for i, j in edges]
    adjr = [[] for _ in range(len(adj))]
    for a, b in edgesr:
        adjr[a].append(b)
    return adjr



def explore(adj, v, visited, path, clock, pre, post):
    visited[v] = True
    path.append(v)
    pre[v] = clock
    clock += 1

    for w in adj[v]:
        if (visited[w] is None):
            explore(adj, w, visited, path, clock, pre, post)

    post[v] = clock
    clock += 1


def dfs(adj, visited, clock, pre, post):
    n = len(adj)

    for v in range(n):
        if visited[v] is None:
            explore(adj, v, visited, path, clock, pre, post)








def acyclic(adj):


    visited = [None for _ in range(len(adj))]

    adjr = reverseg(adj)


    return 0


edges = [[1, 2], [2, 3], [1, 3], [3, 4], [1, 4], [2, 5], [3, 5]]
edges2 = [[], [], [], [], []]
edges1 = [[1, 2], [4, 1], [2, 3], [3, 1]]

adj = [[] for _ in range(4)]

for (a, b) in edges1:
    adj[a - 1].append(b - 1)
    #adj[b - 1].append(a - 1)
clock = 1
pre = [None for _ in range(len(adj))]
post = [None for _ in range(len(adj))]
visited = [None for _ in range(len(adj))]
path = []

#explore(adj, 0, visited, cc, ccnum)
#print(dfs(adj, visited), acyclic(adj))
v = 0
print(adj)
print(dfs(adj, visited, clock, pre, post))
print(pre)
print(post)
print(path)

Привет, пожалуйста, помогите проверить этот код, я ввел псевдокод, но вывод прежнего и поствитированного номера неправильный. Моя задача - найти цикл в графе, поэтому мне нужно сначала найти сильно связанные компоненты, запустить dfs в перевернутом графе и исследовать вершину с наибольшим номером в исходном графе. Я застрял в номере №

Answer 1

Этот код основан на псевдокоде, который является алгоритмом поиска по глубине (DFS) для поиска в графе, и я собираюсь использовать его для поиска сильно связанных компонентов (SCC) в графе:

Explore(v):
  visited(v) ← true
  previsit(v)
  for (v,w) ∈ E:
     if not visited(w):
        explore(w)
  postvisit(v)

и здесь:

previsit(v):
  pre(v) ← clock
  clock ← clock + 1
postvisit(v):
  post(v) ← clock
  clock ← clock + 1

часы здесь должны быть глобальной переменной.