Problem p03108 (python)

Fixed submission:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a == -1:
        a,b,A,B = b,a,B,A
    if b==-1:
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] += connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = [-1]*N
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa += dfubensa[i]
    print(fubensa)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_size(self,n):
        p = self.get_Parent(n)
        return self.size[p]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.size[x] += self.size[y]
            self.Parent[y] = x
            return True
        return False
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

ans = [0]
T = UnionFind(N)
for a,b in AB[::-1]:
    a-=1;b-=1
    ans.append(ans[-1])
    A = T.get_size(a)
    B = T.get_size(b)
    if T.merge(a,b):
        C = T.get_size(a)
        ans[-1] += (C*(C-1)-A*(A-1)-B*(B-1))//2

a0 = ans[-1]
for o in ans[-2::-1]:print(a0-o)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_size(self,n):
        p = self.get_Parent(n)
        return self.size[p]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.size[x] += self.size[y]
            self.Parent[y] = x
            return True
        return False
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

ans = [0]
T = UnionFind(N)
for a,b in AB[::-1]:
    a-=1;b-=1
    ans.append(ans[-1])
    A = T.get_size(a)
    B = T.get_size(b)
    if T.merge(a,b):
        C = T.get_size(a)
        ans[-1] -= (A*(A-1)+B*(B-1))//2
        ans[-1] += (C*(C-1))//2

a0 = ans[-1]
for o in ans[-2::-1]:print(a0-o)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a==-1:
        a,b = b,a
        A,B = B,A
    if b==-1:
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] = connect[a] + connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = -np.ones(N,dtype=int)
dfubensa = np.zeros(M,dtype=int)
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa = fubensa+ dfubensa[i]
    print(fubensa)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = np.zeros(M,dtype=int)
B = np.zeros(M,dtype=int)
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())


def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a==-1 or b==-1:
        if a==-1:
            a = b
            A,B = B,A
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] = connect[a] + connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = [-1]*N
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa = fubensa+ dfubensa[i]
    print(fubensa)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = np.zeros(M,dtype=int)
B = np.zeros(M,dtype=int)
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())


%%timeit
def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a==-1 or b==-1:
        if a==-1:
            a = b
            A,B = B,A
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] = connect[a] + connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = [-1]*N
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa = fubensa+ dfubensa[i]
    print(fubensa)