Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

# Union-Find
def root(i):
    if node_groups[i] == i:
        return i
    else:
        node_groups[i] = root(node_groups[i])
        return node_groups[i]

def same(a, b):
    return root(a) == root(b)

def size(i):
    return group_sizes[root(i)]

def unite(a, b):
    a = root(a)
    b = root(b)

    if a == b:
        return

    if group_ranks[a] < group_ranks[b]:
        group_sizes[b] += size(a)
        node_groups[a] = b
    else:
        group_sizes[a] += size(b)
        node_groups[b] = a
        if group_ranks[a] == group_ranks[b]:
            group_ranks[a] += 1


n,m,k = get_nums_l()

lines = list(map(lambda s: s.strip(), sys.stdin.readlines()))
friends = list(map(lambda s: list(map(int, s.split())), lines[:m]))
blocks = list(map(lambda s: list(map(int, s.split())), lines[m:]))


nodes = n+1
node_groups = [ i for i in range(nodes)]
group_sizes = [ 1 for _ in range(nodes)]
group_ranks = [ 0 for _ in range(nodes)]

edges = []
for f in friends:
    unite(f[0], f[1])

group_nodes = [set() for _ in range(nodes)]
for node in range(1, n+1):
    group_nodes[root(node)].add(node)

kouho = [0] * nodes
for node in range(1, n+1):
    kouho[node] = (len(group_nodes[root(node)]) -1 )
# log("kouhoA", kouho)

for fr in friends:
    kouho[fr[0]] -= 1
    kouho[fr[1]] -= 1
for bl in blocks:
    if same(bl[0], bl[1]):
        kouho[bl[0]] -= 1
        kouho[bl[1]] -= 1

print(" ".join(map(str, kouho[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xとyを統合する
    def union(self, x, y):
        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):
        return -self.parents[self.find(x)]

    # xとyが同じグループかどうか判定する
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xのメンバーの要素を返す
    def members(self, 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())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())

uf = UnionFind(N)
FRIEND = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1

    uf.union(a, b)
    FRIEND[a] += 1
    FRIEND[b] += 1

BLOCK = [0] * N

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1

    if uf.same(c, d):
        BLOCK[c] += 1
        BLOCK[d] += 1


ANS = []
for i in range(N):
    r = uf.size(i)
    r -= FRIEND[i]
    r -= BLOCK[i]
    r -= 1
    ANS.append(str(r))

print(' '.join(ANS))

Submission status: Accepted

Solution code:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt

import sys
input = sys.stdin.readline
n, m, k = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]

info2 = [list(map(int, input().split())) for i in range(k)]


graph = [[] for i in range(n)]
uf = UnionFind(n)
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    uf.merge(a, b)

graph2 = [[] for i in range(n)]
for i in range(k):
    a, b = info2[i]
    a -= 1
    b -= 1
    if uf.is_same(a, b):
        graph2[a].append(b)
        graph2[b].append(a)

ans = [0] * n
for i in range(n):
    ans[i] = uf.get_size(i) - len(graph[i]) - 1 - len(graph2[i])
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

n, m, k = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        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):
        return -self.parents[self.find(x)]

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

    def members(self, 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())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

friend_uf = UnionFind(n)

count_friend = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    count_friend[a-1] += 1
    count_friend[b-1] += 1
    friend_uf.union(a-1, b-1)

ans = [0 for _ in range(n)]
for i in range(1, n+1):
    ans[i-1] = friend_uf.size(i-1) - count_friend[i-1] - 1

for i in range(k):
    c, d = map(int, input().split())
    if friend_uf.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

out = []
for i in range(n):
    out.append(str(max(ans[i], 0)))

print(" ".join(out))

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N,M,K = map(int, input().split())

    ds = [i for i in range(N+1)]
    cntOfF = [0]*(N+1)
    blocks = [set() for _ in range(N+1)]

    for _ in range(M):
        a, b = map(int, input().split())
        dsUnion(ds, a, b)
        cntOfF[a] += 1 
        cntOfF[b] += 1 

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

    Q = {}
    for i in range(1, N+1):
        root = dsFind(ds, i)
        if not(root in Q):
            Q[root] = set()

        Q[root].add(i)
    
    X = []
    for i in range(1, N+1):
        root = dsFind(ds, i)
        q = Q[root]
        block = blocks[i]

        x = len(q) - 1 - cntOfF[i] - len(q&block)
        X.append(x)

    print(' '.join(map(str, X)))



main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        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):
        return -self.parents[self.find(x)]

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

    def members(self, 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())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

U=UnionFind(n)
friend=[0]*n
block=[0]*n
for _ in range(m):
    a,b=map(int,input().split())
    U.union(a-1,b-1)
    friend[a-1]+=1
    friend[b-1]+=1
ans=[0]*n
for i in range(n):
    ans[i]=U.size(i)-friend[i]-1
for _ in range(k):
    c,d=map(int,input().split())
    if U.same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.mini = [i for i in range(n+1)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        mini = min(self.mini[x], self.mini[y])
        self.mini[x] = mini
        self.mini[y] = mini

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


def main():
    N, M, K = ints_raw()
    friends = [[] for _ in range(N)]
    blocks = [[] for _ in range(N)]
    friUF = UnionFind(N)
    for _ in range(M):
        A,B = ints_raw()
        A-=1
        B-=1
        friends[A].append(B)
        friends[B].append(A)
        friUF.union(A,B)
    for _ in range(K):
        C,D = ints_raw()
        C-=1
        D-=1
        blocks[C].append(D)
        blocks[D].append(C)
    group = [0 for _ in range(N)]
    for n in range(N):
        g = friUF.find(n)
        group[g]+=1
    ans = []
    for n in range(N):
        g = friUF.find(n)
        ng = group[g]
        ng -= len(friends[n])
        ng -= len([d for d in blocks[n] if friUF.find(d)==g])
        ans.append(ng-1)
    return " ".join([str(a) for a in ans])


print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  # 親が自分ならroot
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  # 親をrootに付け替える
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  # ランクが高い方を親にする。
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def getElementCount(self):  # 要素ごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return [counts[r] - 1 for r in roots]

    def getRootCount(self):  # ルートごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return counts


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    N, M, K = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    friend_grid = [[int(x) - 1 for x in sys.stdin.readline().split()]
                   for _ in range(M)]  # int grid

    block_grid = [[int(x) - 1 for x in sys.stdin.readline().split()]
                  for _ in range(K)]  # int grid

    uf = UnionFind(N)
    for a, b in friend_grid:
        uf.unite(a, b)

    count_list = uf.getElementCount()

    for a, b in friend_grid:
        count_list[a] -= 1
        count_list[b] -= 1

    for c, d in block_grid:
        if uf.isSame(c, d):
            count_list[c] -= 1
            count_list[d] -= 1

    print(' '.join([str(c) for c in count_list]))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd

sys.setrecursionlimit(10**7)
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)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*(n)
        self.size = [1]*(n)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

#uni = UnionFind(10)
#print('par', uni.par)
#print('1-4', uni.same_check(1,4))
#print('union', uni.union(1,4))
##print('par', uni.par)
##print('1-4', uni.same_check(1,4))

uni = UnionFind(N)
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    uni.union(a, b)

res = [uni.get_size(x)-1 for x in range(N)]

for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    res[a] -= 1
    res[b] -= 1

for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    if uni.same_check(c, d):
        res[c] -= 1
        res[d] -= 1

print(*res)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2 * 10 ** 9)

n, m, k = map(int, input().split())

def dfs(u):
    if visited[u]:
        return

    visited[u] = True

    for v in graph[u]:
        s.add(v)
        dfs(v)

graph = {i: set() for i in range(n)}
blocks = {i: set() for i in range(n)}

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    graph[a].add(b)
    graph[b].add(a)

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

    blocks[c].add(d)
    blocks[d].add(c)

ans = [0] * n

visited = [False] * n

for u in range(n):
    if not visited[u]:
        s = set()

        dfs(u)

        l = len(s)

        for i in s:
            ans[i] += l - 1
            ans[i] -= len(blocks[i].intersection(s))
            ans[i] -= len(graph[i].intersection(s))

print(*ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ
        self.blocksize = [0] * N

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def block(self, x, y):
        if not self.has_same_parent(x, y):
            return
        self.blocksize[x] += 1
        self.blocksize[y] += 1

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


N, M, K = MI()
uf = UnionFind(N)
nl = [set() for _ in range(N)]
for _ in range(M):
    A, B = MI()
    nl[A - 1].add(B - 1)
    nl[B - 1].add(A - 1)
    uf.unite(A - 1, B - 1)

for _ in range(K):
    C, D = MI()
    uf.block(C - 1, D - 1)


ans = []
for i in range(N):
    a = uf.size[uf.find(i)] - len(nl[i]) - uf.blocksize[i] - 1
    ans.append(str(a))
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, 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())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
	N, M, K = MAP()
	friends = defaultdict(list)
	tree = UnionFind(N)
	for _ in range(M):
		A, B = MAP()
		tree.union(A-1, B-1)
		friends[A-1].append(B-1)
		friends[B-1].append(A-1)

	blocks = defaultdict(list)
	for _ in range(K):
		C, D = MAP()
		blocks[C-1].append(D-1)
		blocks[D-1].append(C-1)

	for i in range(N):
		minus = 0
		for b in blocks[i]:
			if tree.same(i, b):
				minus += 1
		print(tree.size(i)-len(friends[i])-1-minus, end=" ")
	print()

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
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)]

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for a, b in ab:
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

for c, d in cd:
    block[c-1].append(d-1)
    block[d-1].append(c-1)


class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]

uft = UnionFind(n)
for a, b in ab:
    ra = uft.find_root(a - 1)
    rb = uft.find_root(b - 1)
    if ra != rb:
        uft.unite(ra, rb)

ans = []
for i in range(n):
    temp = uft.get_size(i) - 1
    rx = uft.find_root(i)
    for y in friend[i]:
        if uft.find_root(y) == rx:
            temp -= 1
    for y in block[i]:
        if uft.find_root(y) == rx:
            temp -= 1
    ans.append(str(temp))

print(' '.join(ans))

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

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

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			if self.same_check(x, y) != True:
				self.size[y] += self.size[x]
				self.size[x] = 0
			self.par[x] = y
		else:
			if self.same_check(x, y) != True:
				self.size[x] += self.size[y]
				self.size[y] = 0
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

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

#処理内容
def main():
	N, M, K = getlist()

	Dnode = defaultdict(int)
	UF = UnionFind(N)
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		Dnode[A] += 1
		Dnode[B] += 1
		UF.union(A, B)

	for i in range(N):
		UF.par[i] = UF.find(i)

	Dblock = defaultdict(int)
	for i in range(K):
		C, D = getlist()
		C -= 1; D -= 1
		if UF.same_check(C, D):
			Dblock[C] += 1
			Dblock[D] += 1

	ans = [0] * N
	for i in range(N):
		ans[i] = UF.siz(i) - 1 - Dblock[i] - Dnode[i]

	print(" ".join(list(map(str, ans))))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        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):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            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
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    N, M, K = map(int, input().split())
    UF = UnionFind(N+1)
    fr_num = [0] * (N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        UF.unite(a, b)
        fr_num[a] += 1
        fr_num[b] += 1

    ans = [0] * (N+1)
    for i in range(1, N+1):
        ans[i] = UF.size(i) - 1 - fr_num[i]

    for _ in range(K):
        c, d = map(int, input().split())
        if UF.isSameGroup(c, d):
            ans[c] -= 1
            ans[d] -= 1
    print(*ans[1:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def find(self, x):
        if self.parent[x] == x:
            return x
        # path compression
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        # union by size
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]
N,M,K = map(int,input().split())
uf = UnionFind(N)
connect = [0]*N
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    connect[a] += 1
    connect[b] += 1
    uf.unite(a,b)
anss = [uf.sizeofset(i)-connect[i]-1 for i in range(N)]
for i in range(K):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
       anss[c] -= 1
       anss[d] -= 1
print(*anss)