Problem p03108 (python)

Fixed submission:
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(20000)
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
    import sys
    sys.setrecursionlimit(3000)
    n,m = map(int,input().split())
    a = [0]*m
    b = [0]*m
    for i in range(m):
      u,v = map(int, input().split())
      a[i] = u-1
      b[i] = v-1
    par = [i for i in range(n)]
    size = [1]*n
    incomb = [n*(n-1)//2]*m
     
    def root(x):
      if par[x] == x: 
        return x
      else:
        par[x] = root(par[x])
        return par[x]
        
    def isSame(x,y):
      return par[x] == par[y]
     
    def union(x,y):
      x = root(x)
      y = root(y)
      if x == y:
        return
      else:
        par[y] = x
        size[x] += size[y]
        
    def size_count(x):
      return size[root(x)]
     
    for i in reversed(range(1,m)):
      q_a = a[i]
      q_b = b[i]
      size_a = size_count(q_a)
      size_b = size_count(q_b)
      if not isSame(q_a,q_b):
        union(q_a,q_b)
        incomb[i-1] = incomb[i] - size_a*size_b
      else:
        incomb[i-1] = incomb[i]
     
    for i in incomb:
      print(i)

Buggy submission (verdict: Runtime Error):
    import sys
    sys.setrecursionlimit(100000)
    n,m = map(int,input().split())
    a = [0]*m
    b = [0]*m
    for i in range(m):
      u,v = map(int, input().split())
      a[i] = u-1
      b[i] = v-1
    par = [i for i in range(n)]
    size = [1]*n
    incomb = [n*(n-1)//2]*m
     
    def root(x):
      if par[x] == x: 
        return x
      else:
        par[x] = root(par[x])
        return par[x]
        
    def isSame(x,y):
      return par[x] == par[y]
     
    def union(x,y):
      x = root(x)
      y = root(y)
      if x == y:
        return
      else:
        par[y] = x
        size[x] += size[y]
        
    def size_count(x):
      return size[root(x)]
     
    for i in reversed(range(1,m)):
      q_a = a[i]
      q_b = b[i]
      size_a = size_count(q_a)
      size_b = size_count(q_b)
      if not isSame(q_a,q_b):
        union(q_a,q_b)
        incomb[i-1] = incomb[i] - size_a*size_b
      else:
        incomb[i-1] = incomb[i]
     
    for i in incomb:
      print(i)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
import math

def comb(n, r):
  if n >=r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
      
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [comb(n,2)]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
import math

def comb(n, r):
  if n >=r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
      
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [comb(n,2)]*(m+1)

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i] = incomb[i+1] - size_a*size_b
  else:
    incomb[i] = incomb[i+1]
incomb.pop(0)
for i in incomb:
  print(i)

Buggy submission (verdict: Runtime Error):
import math

def comb(n, r):
  if n >=r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
  
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
set_len =[n]
island = [0]*n
incomb = [comb(n,2)]*(m+1)
name=1
for i in reversed(range(m)):
  a_l = island[a[i]]
  b_l = island[b[i]]
  if a_l == b_l and a_l != 0: 
    pass
  elif a_l > 0 and b_l > 0:
    id_min = min(a_l,b_l)
    id_max = max(a_l,b_l)
    for j in range(n):
      if island[j] == id_max:
        island[j] = id_min
    pop = set_len.pop(id_max)
    set_len[id_min] += pop
  elif a_l > 0 : 
    island[b[i]] = a_l
    set_len[a_l] += 1
    set_len[0] -= 1
  elif b_l > 0:
    island[a[i]] = b_l
    set_len[b_l] += 1
    set_len[0] -= 1
  else:
    island[a[i]] = name
    island[b[i]] = name
    set_len.append(2)
    set_len[0] -= 2
    name += 1
  for j in range(1,len(set_len)):
    incomb[i] -= comb(set_len[j],2) 

incomb.pop(0)
for i in incomb:
 print(i)