Problem p03108 (python)

Fixed submission:
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    if n_a > n_b:
      roots[root_a] = (root_a, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_a, n_a + n_b)
    else:
      roots[root_a] = (root_b, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    roots[root_a] = (root_b, n_a + n_b) # 二項目は何でも良い
    roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    roots[root_a] = (root_b, n_a + n_b) # 二項目は何でも良い
    roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    roots[root_a] = (b, None) # 二項目は何でも良い
    roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    roots[root_a] = (b, None) # 二項目は何でも良い
    roots[root_b] = (b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A=[0] * M
B=[0] * M

import math

for i in range(M):
  A[i], B[i] = list(map(int, input().split()))

  
island_dict = [i for i in range(N+1)] #{i+1:i+1 for i in range(N)} #島が属するグループ
#group_dict = [[i] for i in range(N+1)] #{i+1:[i+1] for i in range(N)} #グループに属する島
group_len_dict= [1 for i in range(N+1)] #{i+1:1 for i in range(N)}

answer = [0] * M
answer[-1] = math.factorial(N) // (math.factorial(N-2)*2)
  
for i in range(M)[:0:-1]:
  if island_dict[A[i]] == island_dict[B[i]]:
    answer[i-1] = answer[i]
  else:
    groupA = island_dict[A[i]]
    groupB = island_dict[B[i]] #グループ合併, groupB消滅
    NA = group_len_dict[groupA]
    NB = group_len_dict[groupB]
    
    if NA>=NB:
      island_dict = [groupA if g==groupB else g for g in island_dict]
      #for j in group_dict[groupB]:
      #  island_dict[j] = groupA
      #group_dict[groupA] = group_dict[groupA] + group_dict[groupB]
      #group_dict[groupB] = []
      group_len_dict[groupA] = group_len_dict[groupA] + group_len_dict[groupB]
      #group_len_dict[groupB] = 0
      
    else:
      island_dict = [groupB if g==groupA else g for g in island_dict]
      #for j in group_dict[groupA]:
      #  island_dict[j] = groupB
      group_dict[groupB] = group_dict[groupA] + group_dict[groupB]
      #group_dict[groupA] = []
      group_len_dict[groupB] = group_len_dict[groupA] + group_len_dict[groupB]
      #group_len_dict[groupA] = 0
      
    answer[i-1] = answer[i] - NA*NB

#print(answer)

for i in range(M):
  print(answer[i])

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A=[0] * M
B=[0] * M

import math

for i in range(M):
  A[i], B[i] = list(map(int, input().split()))

  
island_dict = {i+1:i+1 for i in range(N)} #島が属するグループ
group_dict = {i+1:[i+1] for i in range(N)} #グループに属する島

answer = [0] * M
answer[-1] = math.factorial(N) // (math.factorial(N-2)*2)
  
for i in range(M)[:0:-1]:
  if island_dict[A[i]] == island_dict[B[i]]:
    answer[i-1] = answer[i]
  else:
    groupA = island_dict[A[i]]
    groupB = island_dict[B[i]] #グループ合併, groupB消滅
    NA = group_dict[groupA]
    NB = group_dict[groupB]
    
    if NA>=NB:
      for j in group_dict[groupB]:
        island_dict[j] = groupA

      group_dict[groupA] = group_dict[groupA] + group_dict[groupB]
      group_dict[groupB] = []
    else:
      for j in group_dict[groupA]:
        island_dict[j] = groupB

      group_dict[groupB] = group_dict[groupA] + group_dict[groupB]
      group_dict[groupA] = []
    
    answer[i-1] = answer[i] - NA*NB

#print(answer)

for i in range(M):
  print(answer[i])

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A=[0] * M
B=[0] * M

import math

for i in range(M):
  A[i], B[i] = list(map(int, input().split()))

  
island_dict={i+1:i+1 for i in range(N)} #島が属するグループ
group_dict={i+1:1 for i in range(N)} #グループに属する島の数

answer = [0] * M
answer[-1] = math.factorial(N) // (math.factorial(N-2)*2)

  
for i in range(M)[:0:-1]:
  if island_dict[A[i]] == island_dict[B[i]]:
    answer[i-1] = answer[i]
  else:
    groupA = island_dict[A[i]]
    groupB = island_dict[B[i]] #グループ合併, groupB消滅
    NA = group_dict[groupA]
    NB = group_dict[groupB]
    
    for j in group_dict[groupB]:
      island_dict[j] = groupA
   
    group_dict[groupA] = group_dict[groupA] + group_dict[groupB]
    group_dict[groupB] = 0
    answer[i-1] = answer[i] - NA*NB

#print(answer)

for i in range(M):
  print(answer[i])