Problem p02762 (python)

Fixed submission:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.parents[x] = x
        self.sizes[x] += self.sizes[y]
        self.sizes[y] = self.sizes[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1] * (n + 1)

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1] * (n + 1)

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    # if same(c - 1, d - 1):
    #     blocks[c - 1].add(d - 1)
    #     blocks[d - 1].add(c - 1)
    blocks[c - 1].add(d - 1)
    blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    # s = sizes[x]
    s = 0
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y
    # sizes[x] = sizes[x] + sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for i in range(n)]

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y
    sizes[x] = sizes[x] + sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    x = root(x)
    y = root(y)
    return x == y

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
dic = {}

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y

def same(x, y):
    x = root(x)
    y = root(y)
    return x == y

def size(x):
    global parent
    key = root(parent[x])
    s = 0
    for i in range(n):
        if root(parent[i]) == key:
            s += 1
    return s

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = 0
    if x in dic:
        s = dic[x]
    else:
        s = size(x)
        dic[x] = s
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

candidates = [None] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
dic = {}

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y


def group(x):
    global parent
    key = root(parent[x])
    s = set()
    for i in range(n):
        if root(parent[i]) == key:
            s.add(i)
    return s

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c - 1].add(d - 1)
    blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = set()
    if x in dic:
        s = dic[x]
    else:
        s = group(x)
        dic[x] = s
    candidates[i] = str(len(s - friends[i] - blocks[i]) - 1)

print(' '.join(candidates))