Problem p02536 (python)

Fixed submission:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノードxが属するメンバーをリスト形式で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
    #親全てをリスト形式で返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
    #グループ数の合計を返す
        return len(self.roots())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-1)

Buggy submission (verdict: Runtime Error):
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  #print(r)
  #print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_a_par] = city_b
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Buggy submission (verdict: Runtime Error):
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  print(r)
  print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_a_par] = city_b
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
print(r)
print(group_num-1+r.count(-1)-1)

Buggy submission (verdict: Runtime Error):
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  #print(r)
  #print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_b_par] = city_a
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Buggy submission (verdict: Runtime Error):
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    r[city_b_par] = r[city_a]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Buggy submission (verdict: Runtime Error):
def root(x):
  if r[x] < 0:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, x in enumerate(road):
  x1_me = x[0]
  x2_me= x[1]
  x1 = root(x1_me)
  x2 = root(x2_me)
  #print("x1", x1, "x2", x2)
  
  if r[x1] == -1 and r[x2] == -1:
    r[x2] = x1
  elif r[x1] == -1 or r[x2] == -1:
    if r[x1] > r[x2]:
      r[x2] = r[x1]
    else:
      r[x1] = r[x2]
  else:
    if r[x1] > r[x2]:
      r[x1] = r[x2]
    else:
      r[x2] = r[x1]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)