Problem p03142 (python)

Fixed submission:
import sys

sys.setrecursionlimit(100000000)

N, M = list(map(int, input().split()))

AB = [tuple(map(int, input().split())) for _ in range(N + M - 1)]

dprint = print


def BellmanFord(edges, num_v, source):
    # グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source - 1] = 0

    # 辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == num_v - 1: return -1

    return dist


class Tree:
    def __init__(self, n):
        self.parent = set()
        self.child = set()
        self.rank = -1
        self.rank_fix = None
        self.current_parent = -1
        self.n = n

    def add_parent(self, i):
        self.parent.add(i)

    def add_child(self, i):
        self.child.add(i)

    def update_rank(self, v, parent_no):
        if self.rank >= v:
            return
        self.rank = v
        if self.current_parent != -1 and self.current_parent in self.parent:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v + 1, self.n)

    def get_rank(self):
        if self.rank_fix:
            return self.rank_fix
        rank =  -1
        for p in self.parent:
            tmp_rank = trees[p].get_rank()
            if tmp_rank >rank:
                self.current_parent = p
                rank = tmp_rank
        self.rank_fix = rank + 1
        return self.rank_fix

    def __repr__(self):
        return "child" + str(self.child) + "rank:" + str(self.rank_fix) + " p:" + str(self.current_parent)


trees = [Tree(i) for i in range(N + 1)]
ans = [-1 for _ in range(N + 1)]
for a, b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i, t in enumerate(trees):
    if i != 0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        break
# print(trees)
for i in range(N):
    (trees[i + 1].get_rank())
    print(trees[i+1].current_parent)

Buggy submission (verdict: Runtime Error):
N,M = list(map(int,input().split()))

AB = [tuple(map(int,input().split()))for _ in range(N+M-1)]

dprint = print
class tree:
    def __init__(self,n):
        self.parent = set()
        self.child = set()
        self.rank = 0
        self.current_parent = -1
        self.n = n
    def add_parent(self,i):
        self.parent.add(i)
    def add_child(self,i):
        self.child.add(i)
    def update_rank(self,v,parent_no):
        if self.rank >v:
            return
        self.rank=v
        if self.current_parent!=-1 and self.current_parent in self.parent:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v+1,self.n)

    def __repr__(self):
        return "child" + str(self.child) +"rank:" +str(self.rank) + " p:" +str(self.current_parent)

trees = [tree(i) for i in range(N+1)]
ans =[-1 for _ in range(N+1)]
for a,b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i,t in enumerate(trees):
    if i!=0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        trees[0].update_rank(0,0)
        ans[i]=0
        break
for i in range(N):
    print(trees[i+1].current_parent)

Buggy submission (verdict: Runtime Error):
N,M = list(map(int,input().split()))

AB = [tuple(map(int,input().split()))for _ in range(N+M-1)]

dprint = print
class tree:
    def __init__(self,n):
        self.parent = set()
        self.child = set()
        self.rank = 0
        self.current_parent = -1
        self.n = n
    def add_parent(self,i):
        self.parent.add(i)
    def add_child(self,i):
        self.child.add(i)
    def update_rank(self,v,parent_no):
        if self.rank >v:
            return
        self.rank=v
        if self.current_parent!=-1 and self.current_parent!=parent_no:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v+1,self.n)

    def __repr__(self):
        return "child" + str(self.child) +"rank:" +str(self.rank) + " p:" +str(self.current_parent)

trees = [tree(i) for i in range(N+1)]
ans =[-1 for _ in range(N+1)]
for a,b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i,t in enumerate(trees):
    if i!=0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        trees[0].update_rank(0,0)
        ans[i]=0
        break
for i in range(N):
    print(trees[i+1].current_parent)