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:
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())


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

# 友達関係をUFで用意
uf = UnionFind(N)

# 直接の友達のリスト
friend = [[] for i in range(N)]
# 直接のブロックのリスト
block = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

ans = [0 for i in range(N)]

# 友達関係のグループの要素数ーグループ内の直接の友達の数ーグループ内の直接のブロックの数ー自分自身
for i in range(N):
    ans[i] += uf.size(i) -1
    for j in friend[i]:
        if uf.same(i,j):
            ans[i] -= 1
    for j in block[i]:
        if uf.same(i,j):
            ans[j] -= 1

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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
F = [list() for _ in range(N)]
B = [list() for _ in range(N)]

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

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

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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

UF = UnionFind(N)

for i in range(N):
    for friend in F[i]:
        UF.union(i, friend)

ans = [UF.size[UF.find(i)] - 1 for i in range(N)]

for i in range(N):
    ans[i] -= len(F[i])

for i in range(N):
    for block in B[i]:
        if UF.same(i,block):
            ans[i] -= 1

print(*ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    __slots__ = ('__parents', )

    def __init__(self, n):
        self.__parents = [-1] * n

    def find(self, x):
        p = self.__parents
        if p[x] < 0:
            return x
        parent = self.find(p[x])
        p[x] = parent
        return parent

    def union(self, x, y):
        p = self.__parents
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if p[x] > p[y]:
            x, y = y, x
        p[x] += p[y]
        p[y] = x
        return True

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

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


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, k = spline()
    similar = UnionFindTree(n)
    candidates = [-1] * n
    for _ in range(m):
        a, b = spline()
        a -= 1
        b -= 1
        similar.union(a, b)
        candidates[a] -= 1
        candidates[b] -= 1
    for i in range(n):
        candidates[i] += similar.size(i)
    for _ in range(k):
        c, d = spline()
        c -= 1
        d -= 1
        if similar.same(c, d):
            candidates[c] -= 1
            candidates[d] -= 1
    print(*candidates, sep=' ')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFindTree:
    __slots__ = ('__parents', )

    def __init__(self, n):
        self.__parents = [-1] * n

    def find(self, x):
        p = self.__parents
        if p[x] < 0:
            return x
        parent = self.find(p[x])
        p[x] = parent
        return parent

    def union(self, x, y):
        p = self.__parents
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if p[x] > p[y]:
            x, y = y, x
        p[x] += p[y]
        p[y] = x
        return True

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

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


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, k = spline()
    similar = UnionFindTree(n)
    candidates = [-1] * n
    kw = {'func_': lambda x: int(x) - 1}
    for _ in range(m):
        a, b = spline(**kw)
        similar.union(a, b)
        candidates[a] -= 1
        candidates[b] -= 1
    for i in range(n):
        candidates[i] += similar.size(i)
    for _ in range(k):
        c, d = spline(**kw)
        if similar.same(c, d):
            candidates[c] -= 1
            candidates[d] -= 1
    print(*candidates, sep=' ')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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())
      
n, m, k = map(int, input().split())
uf = UnionFind(n)
E = [[] for i in range(n)]
num_E = [0]*n
E_d = [[] for i in range(n)]

import sys
input = sys.stdin.readline

for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uf.union(a, b)
  num_E[a] += 1
  num_E[b] += 1

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  E_d[a] = E_d[a] + [b]
  E_d[b] = E_d[b] + [a]

num_men = [0]*n
for i in range(n):
  num_men[i] = uf.size(i) - 1
  for dn in E_d[i]:
    if uf.same(i, dn):
      num_men[i] -= 1
  num_men[i] -= num_E[i]
      
print(*num_men)

Submission status: Accepted

Solution code:
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # parents
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # find(x)
    # 要素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]

    # union(x, y)
    # 要素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

    # same(x, y)
    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # size(x)
    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

import sys
def input():
    return sys.stdin.readline().strip()

n, m, k = map(int, input().split())
ans = [-1 for _ in range(n)]
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    ans[a-1] -= 1
    ans[b-1] -= 1

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

for i in range(n):
    ans[i] += uf.size(i)

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

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
frag=list(range(n+1))

def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p
    
ans=[-1]*(n+1)
for i in range(m):
    a,b = map(int,input().split())
    ans[a]-=1
    ans[b]-=1
    a,b = takefrag(a),takefrag(b)
    a,b = min(a,b),max(a,b)
    frag[a]=b

fragteam=[0]*(n+1)
for i in range(n+1):
    frag[i]=takefrag(i)
    fragteam[frag[i]]+=1
for i in range(k):
    a,b = map(int,input().split())
    if frag[a]==frag[b]:
        ans[a]-=1
        ans[b]-=1
for i in range(n+1):
    ans[i]+=fragteam[frag[i]]
for i in ans[1:-1]:
    print(i,end=" ")
print(ans[-1])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, data):
        """
        サイズベースのunion_find
        与えられたdataまでの長さの配列を作成
        配列は1から開始する
        それがunionfindの親となり初めは自分自身
        またsizeも定義し初期値は1
        ・union findのグループのサイズの求め方
        1.あるxのグループの親を取得
        union_find = UnionFind(N)
        par_x = union_find.find(x)
        2.その親のsizeがそのグループのサイズになっている
        size = union_find.size[par_x]
        """
        self.parent = {}
        self.size = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.size[i] = 1


    def find(self, x):
        """
        与えられた値に対してその親ノードを返却
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) # self.parentに入れ直しているのは次findするとき高速になるよう再起により親を直接結んでいる
            return self.parent[x]


    def same(self, x, y):
        """
        与えられた2つの値が同一グループ(親)かチェック
        """
        return self.find(x) == self.find(y)


    def unite(self, x, y):
        """
        与えられた2つの値を同一のグループ(親)にする
        """
        x = self.find(x)
        y = self.find(y)
        if x == y: # すでに同じグループなら何もしない
            return
        if self.size[x] > self.size[y]: # ランクが異なる場合小さい方の親を大きい方にする
            self.parent[y] = x
            self.size[x] += self.size[y]
            return
        elif self.size[x] < self.size[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
            return
        else: # ランクが同じ場合どちらかの親にする その際親にした方の値のランクをあげる
            self.parent[x] = y
            if self.size[x] == self.size[y]: self.size[y] += self.size[x]
            return

if __name__ == '__main__':
    N,M,K = map(int, input().split())
    union_find = UnionFind(N)

    kankei = [[] for i in range(N+1)]
    for i in range(M):
        A,B = map(int, input().split())
        union_find.unite(A,B)
        kankei[A].append(B)
        kankei[B].append(A)

    for i in range(K):
        C,D = map(int, input().split())
        if union_find.same(C,D):
            kankei[C].append(D)
            kankei[D].append(C)

    ans = ""
    for i in range(1,N+1):
        ans += str(union_find.size[union_find.find(i)]-len(kankei[i])-1) + " "

    print(ans.rstrip())

Submission status: Accepted

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

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        dq = deque()
        dq.append(v)
        while dq:
            v = dq.popleft()
            r = roots[v]
            for u in fs[v]:
                if ~roots[u]: continue
                roots[u] = r
                dq.append(u)

    sizes = [0] * N
    for r in roots:
        sizes[r] += 1

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    input = sys.stdin.readline

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    sizes = [-1] * N

    def dfs(v):
        """
        return: 連結成分のサイズを返す
        roots: 連結成分の各成分に根のindexを割り当てる
        """
        sz = 1
        for u in fs[v]:
            if ~roots[u]: continue
            roots[u] = roots[v]
            sz += dfs(u)
        return sz

    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        sizes[v] = dfs(v)

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        # 全て根 (par[x] = x) として初期化
        self.par = list(range(n))
        self.siz = [1] * n
    
    def root(self, x):
        """データxが属する木の根を再帰で得る
        """
        if self.par[x] == x: return x  # 根ならそのまま返す
        self.par[x] = self.root(self.par[x])  # 経由したノード全ての親を上書き
        return self.par[x]

    def size(self, x):
        """データxが属する木のサイズを返す
        """
        return self.siz[self.root(x)]
    
    def unite(self, x, y):
        """xとyの木を併合する
        """
        rx, ry = self.root(x), self.root(y)
        if rx != ry:  # xとyの根が違う (=違う木である) 場合
            if self.siz[rx] < self.siz[ry]: rx, ry = ry, rx  # xの木の方が大きくなるようにする
            self.siz[rx] += self.siz[ry]
            self.par[ry] = rx  # yの根をxの根につける

    def same(self, x, y):
        """2つのデータx, yが属する木が同じならTrueを返す
        """
        rx, ry = self.root(x), self.root(y)
        return rx == ry

n, m, k = map(int, input().split())
uf = UnionFind(n)
n_friends = [0] * n
n_blocks = [0] * n

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

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

ans = []
for i in range(n):
    ans.append(uf.size(i) - n_friends[i] - n_blocks[i] - 1)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    blocks[c-1].append(d-1)
    blocks[d-1].append(c-1)


grp_idx = [-1]*n
grp_szs = []
grp = 0
for i in range(n):
    if grp_idx[i]>=0:
        continue
    queue = deque([i])
    grp_idx[i] = grp
    tmp = 0
    while len(queue)>0:
        node = queue.popleft()
        for c_node in friends[node]:
            if grp_idx[c_node]>=0:
                continue
            grp_idx[c_node] = grp
            tmp += 1
            queue.append(c_node)
    grp_szs.append(tmp)
    grp += 1
ans = []
for i in range(n):
    tmp = grp_szs[grp_idx[i]]
    for j in friends[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    for j in blocks[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    ans.append(tmp)
print(*ans)

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**5)
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    F.unite(a, b)
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# print(f)
for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M,K = map(int,input().split())
F = {i:set() for i in range(1,N+1)}
B = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    F[a].add(b)
    F[b].add(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].add(d)
    B[d].add(c)
A = []
hist = [-1 for _ in range(N+1)]
cnt = -1
for i in range(1,N+1):
    if hist[i]<0:
        cnt += 1
        A1 = set()
        que = deque([i])
        hist[i] = cnt
        A1.add(i)
        while que:
            x = que.popleft()
            for y in F[x]:
                if hist[y]<0:
                    A1.add(y)
                    que.append(y)
                    hist[y]=cnt
        A.append(A1)
C = []
for i in range(1,N+1):
    cnt = hist[i]
    a = A[cnt]&B[i]
    C.append(len(A[cnt])-len(F[i])-len(a)-1)
print(*C)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        # 親の名(いない場合はNone)
        self.parent = [None]*n
        # 子の数
        self.count = [0] * n

    def root(self, x):
        # xの根を返す
        if self.parent[x] == None:
            return x
        else:
            return self.root(self.parent[x])

    def union(self, x, y):
        # xとyをまとめる
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0
        self.count[x0] += self.count[y0] + 1

    def size(self, x):
        # xの属する木の大きさ
        return self.count[self.root(x)] + 1

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
# F[i]=iの友達の数
F = [0]*n
# B[i]=iと同じグループでブロックしている数
B = [0]*n
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    F[a-1] += 1
    F[b-1] += 1
for j in range(k):
    a, b = map(int, input().split())
    if uf.same(a-1, b-1):
        B[a-1] += 1
        B[b-1] += 1
L = [uf.size(i)-1-F[i]-B[i] for i in range(n)]
print(*L)

Submission status: Accepted

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

class Union_Find:
    def __init__(self, n = 0):
        self.d = [-1] * n

    def find_root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.find_root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def size(self, x: int) -> int:
        return (-1) * self.d[self.find_root(x)]

n, m, k = map(int, input().split())
uf = Union_Find(n)
ng = [set() for _ in range(n)]

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

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.is_same(c, d):
        ng[c].add(d)
        ng[d].add(c)

ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - len(ng[i]) - 1

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            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 False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

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

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

    def is_root(self, x):
        return self.parent[x] < 0


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

friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]
UF = UnionFind(n)

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

for j in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blocks[a].append(b)
    blocks[b].append(a)

for i in range(n):
    num = UF.size(i) - 1
    for j in blocks[i]:
        if UF.same(i, j):
            num -= 1
    num -= len(friends[i])
    print(num, end=' ')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
ab,cd=[],[]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  uf.union(a,b)
  ab.append((a,b))
for i in range(k):
  c,d=map(int,input().split())
  c-=1
  d-=1
  cd.append((c,d))
ans=[]
for i in range(n):
  t=uf.count_member(i)-1
  ans.append(t)
for a,b in ab:
  if uf.same(a,b):
    ans[a]-=1
    ans[b]-=1
for c,d in cd:
  if uf.same(c,d):
    ans[c]-=1
    ans[d]-=1
print(*ans)

Submission status: Accepted

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

#友達候補：　ブロック関係にない　友達ではない　間接的に友達
#友達候補＝友達の輪　ー　友達
#ブロックリストが友達の輪とsamegroupだったら−１

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を見てくっつける方を決める
      #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)]
  
uni=UnionFind(N)
fri=[[] for _ in range(N)]
blo=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int, input().split())
  uni.Unite(a-1,b-1)
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d=map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
  
for i in range(N):
  ans=uni.Count(i)-len(fri[i])-1
  for a in blo[i]:
    if uni.isSameGroup(i,a):
      ans-=1
  print(ans, end=" ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc157/tasks/abc157_d
# 友達でつながっている集合を管理する必要
# ブロック関係のときはカウントしない
# すでに友達ならばカウントしない
N, M, K = read_ints()

# iについての友達候補数=同じグループの人数-1 -すでに友達(グループ内で)-すでにブロック(グループ内で)

uf = UnionFind(N)
n_friends = [0] * N
n_blocked = [0] * N
for _ in range(M):
    a, b = read_ints()
    a -= 1
    b -= 1
    uf.unite(a, b)
    n_friends[a] += 1
    n_friends[b] += 1
for _ in range(K):
    c, d = read_ints()
    c -= 1
    d -= 1
    if uf.is_in_same(c, d):
        n_blocked[c] += 1
        n_blocked[d] += 1

ans = []
for i in range(N):
    ans.append(uf.size(i) - n_friends[i] - n_blocked[i] - 1)
print(*ans)