Problem p03108 (python)

Fixed submission:
N,M=[int(x) for x in input().split()]
G=[-1] * N
W=[0] * N
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,j):
    gi=find(i)
    gj=find(j)

    if(gi!=gj):
        if W[gi] > W[gj]:
            G[gi]+=G[gj]
            G[gj]=gi
        else:
            G[gj]+=G[gi]
            G[gi]=gj
            if W[gi]==W[gj]:
                W[gj]+=1

def find(i):
    if G[i]<0:
        return i;
    else:
        G[i]=find(G[i])
        return G[i]

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        ga,gb=find(A),find(B)
        if (ga!=gb):
            ans=ans-(G[ga]*G[gb])
            union(A,B)

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
G=[n for n in range(N)]
W=[1 for n in range(N)]
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        if (Ga!=Gb):
            Wa,Wb=W[Ga],W[Gb]
            ans=ans-(Wa*Wb)
            if (Wb>Wa):
                union(Ga,Gb)
                W[Gb]=Wa+Wb
            else:
                union(Gb,Ga)
                W[Ga]=Wa+Wb
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
G=[n for n in range(N)]
W=[1 for n in range(N)]
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
#    print(E)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        if (Ga!=Gb):
            Wa,Wb=W[Ga],W[Gb]
#        print("%i=%i-(%i*%i)" % (ans-(Wa*Wb),ans,Wa,Wb))
            ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)
        if (Wb>Wa):
            union(Ga,Gb)
            W[Gb]=Wa+Wb
        else:
            union(Gb,Ga)
            W[Ga]=Wa+Wb
#    print(I)
#    print(G)
#    print(W)
#    print("----")

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
G=[n for n in range(N)]
W=[1 for n in range(N)]
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
#    print(E)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        Wa,Wb=W[Ga],W[Gb]
#        print("%i=%i-(%i*%i)" % (ans-(Wa*Wb),ans,Wa,Wb))
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)
        if (Wb>Wa):
            union(Ga,Gb)
            W[Gb]=Wa+Wb
        else:
            union(Gb,Ga)
            W[Ga]=Wa+Wb
#    print(I)
#    print(G)
#    print(W)
#    print("----")

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
G=[n for n in range(N)]
W=[1 for n in range(N)]
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        Wa,Wb=W[Ga],W[Gb]
        if (Wb>Wa):
            union(Ga,Gb)
            W[Gb]=Wa+Wb
        else:
            union(Gb,Ga)
            W[Ga]=Wa+Wb
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
ans = int(N * (N-1) / 2)
E=[]
result=[]
G=[n for n in range(N)]
W=[1 for n in range(N)]

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        Wa,Wb=W[Ga],W[Gb]
        if (Wb>Wa):
            union(Ga,Gb)
            W[Gb]=Wa+Wb
        else:
            union(Gb,Ga)
            W[Ga]=Wa+Wb
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
ans = int(N * (N-1) / 2)
E=[]
result=[]
V=[n for n in range(N)]
W=[1 for n in range(N)]

def union(i,g):
    if(V[i]!=g):
        V[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        Ga=V[A]
        Gb=V[B]
        Wa=W[Ga]
        Wb=W[Gb]
        W[Ga]=Wa+Wb
        W[Gb]=Wa+Wb
        if (Wb>Wa):
            union(A,Gb)
        else:
            union(B,Ga)
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)

Buggy submission (verdict: Runtime Error):
N,M=[int(x) for x in input().split()]
I=[[] for i in range(N)]
E=[]
V=[0 for i in range(N)]

def visit(n):
    total=0
    if (n > -1 and V[n]==0):
        V[n]=1
        total=1
        for i in I[n]:
            total+=visit(i)
    return total

for i in range(M):
    A,B=[int(x) for x in input().split()]
    A,B=A-1,B-1
    I[A].append(B)
    I[B].append(A)
    E.append((A,B))

while len(E)>0:
    A,B=E.pop(0)
    I[A].pop(I[A].index(B))
    I[B].pop(I[B].index(A))
    V=[0 for i in range(N)]

    Z=N
    i=0
    for n in range(N):
        total=visit(n)
        Z=Z-total
        i=i+(total*Z)
    print(i)