Problem p02902 (python)

Fixed submission:
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

N, M = map(int, input().split())
V = list(range(N))
E = [[] for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    edges.append((a-1, b-1))

dag = False
for v in range(N):
    s, prev = cycle_detection(V, E, v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

Buggy submission (verdict: Runtime Error):
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

N, M = map(int, input().split())
E = [[] for i in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    edges.append((a-1, b-1))

dag = False
for v in range(N):
    s, prev = BFS(v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict

def topological_sort(V, E):
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        return top_sorted

N, M = map(int, input().split())
V = list(range(1, N+1))
E1 = defaultdict(list)
E2 = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E1[a].append(b)
    E2[b].append(a)
deleted = topological_sort(V, E1)
if len(deleted) == N: print(-1)
else:
    V = list(set(V) - set(deleted))
    deleted = topological_sort(V, E2)
    V = list(set(V) - set(deleted))
    print(len(V))
    print(*V, sep='\n')