Problem p02762 (python)

Fixed submission:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = UnionFind(n+1)


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    uni.Unite(a, b)

for i in range(k):
    c, d = cd[i]
    if uni.isSameGroup(c,d):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    result.append(uni.Count(i)-con[i])
print(*result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root_b = root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**5)
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2000)
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Buggy submission (verdict: Runtime Error):
import numpy as np
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = np.array([-1 for i in range(n+1)])

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Buggy submission (verdict: Runtime Error):
import numpy as np
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = np.array([-1 for i in range(n+1)])

def root(num, pea, index=True):
    get_index = []
    while pea[num] > 0:
        get_index.append(num)
        num = pea[num]
    if index:
        return num, get_index
    else:
        return num

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a, get_a_index = root(a, uni)
        root_b, get_b_index = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[get_a_index+get_b_index+[root_b]] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni, index=False) == root(d, uni, index=False):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni, index=False)
    result.append(-uni[root_i]-con[i])
print(*result)