Problem p03142 (python)

Fixed submission:
def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    parent = [0]*V
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    while Q:
        del_node = Q.pop()
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)
                parent[j] = del_node+1

    return parent


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    ans = topological_sort(N, E_in, E_from)
    for s in ans:
        print(s)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            if len(an[el]) != 0:
                ret.append(an[el])
            else:
                ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        ans = an[a]
        ans.append(a)
        if all(k in ans for k in l):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]
an = [[] for _ in range(N)]


# 入力
for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)

# 先祖を作る
for i in range(N):
    an[i] = anscestor(i, parent)

for i in range(N):
    if nodes[i] >= 2:
        parent[i] = check(parent[i], parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            if len(an[el]) != 0:
                ret.append(an[el])
            else:
                ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        ans = an[a]
        ans.append(a)
        if all(k in ans for k in l):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]
an = [[] for _ in range(N)]


# 入力
for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)

# 先祖を作る
for i in range(N):
    an[i] = anscestor(i, parent)

for i in range(N):
    if nodes[i] >= 2:
        parent[i] = check(parent[i], parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)

Buggy submission (verdict: Runtime Error):
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            if len(an[el]) != 0:
                ret.append(an[el])
            else:
                ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        ans = an[a]
        ans.append(a)
        if all(k in ans for k in l):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]
an = [[] for _ in range(N)]


# 入力
for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)

# 先祖を作る
for i in range(N):
    an[i] = anscestor(i, parent)

for i in range(N):
    if nodes[i] >= 2:
        parent[i] = check(parent[i], parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)

Buggy submission (verdict: Runtime Error):
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            if len(an[el]) != 0:
                ret.append(an[el])
            else:
                ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        ans = an[a]
        ans.append(a)
        if all(k in ans for k in l):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]
an = [[] for _ in range(N)]


# 入力
for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)

# 先祖を作る
for i in range(N):
    an[i] = anscestor(i, parent)

for i in range(N):
    if nodes[i] >= 2:
        parent[i] = check(parent[i], parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)

Buggy submission (verdict: Runtime Error):
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        b = []
        for j in range(le):
            if not i == j:
                b.append(l[j])

        ans = anscestor(a, parent)
        if all(k in ans for k in b):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]

for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)


for i, n in enumerate(parent):
    if len(n) >= 2:
        parent[i] = check(n, parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)