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:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])

direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

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)]

u = UnionFind(N)
for a,b in AB:
    u.Unite(a, b)

minus_cnt = [0 for i in range(N)]
for a,b in AB:
    minus_cnt[a] += 1
    minus_cnt[b] += 1


for c, d in CD:
    if u.isSameGroup(c,d):
        minus_cnt[c] += 1
        minus_cnt[d] += 1
for i in range(N):
    print(u.Count(i) - 1 - minus_cnt[i], end = " ")

print("")

"""
direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

def dfs(node, p, cluster):
    cluster.append(node)
    if len(direct_friend[node]) == 1:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if len(relation[i]) == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(a, end = " ")
print("")

"""

Submission status: Accepted

Solution code:
class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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の属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        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())

    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_num = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    friend_num[a-1] += 1
    friend_num[b-1] += 1
block = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

ans = []
for i in range(N):
    num = uf.size(i) - friend_num[i] - 1
    for j in block[i]:
        if uf.same(i, j):
            num -= 1
    ans.append(num)
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2 * 10 ** 9)
 
N,M,K = map(int, input().split())

friends = {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
  friends[a].add(b)
  friends[b].add(a)
for _ in range(K):
  a,b = map(int, input().split())
  a-=1;b-=1
  blocks[a].add(b)
  blocks[b].add(a)

ans = [0] * N
visited = [False] * N

def DFS(u):
  if visited[u]:
    return
  visited[u] = True
  for v in friends[u]:
    s.add(v)
    DFS(v)

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(friends[i].intersection(s))
print(*ans)

Submission status: Accepted

Solution code:


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

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

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)

        if xroot == yroot:
            # already same
            return

        if self.size[xroot] < self.size[yroot]:
            # merge to yroot
            self.par[xroot] = yroot
            self.size[yroot] = self.size[xroot] + self.size[yroot]
        else:
            # merge to xroot
            self.par[yroot] = xroot
            self.size[xroot] = self.size[xroot] + self.size[yroot]

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


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

    friend_edge = []
    for _ in range(m):
        friend_edge.append(tuple(map(int, input().split())))

    block_edge = []
    for _ in range(k):
        block_edge.append(tuple(map(int, input().split())))

    return n, friend_edge, block_edge


def submit():
    n, friend_edge, block_edge = read_input()

    # 友達関係をUF
    uf = UnionFind(n)
    for a, b in friend_edge:
        uf.unite(a - 1, b - 1)

    # blockか、friend関係にある要素を整理
    # blockかつ、おなじufに含まれるもののみをのこす　
    remove_dict = {i : 0 for i in range(n)}
    for c, d in block_edge:
        if uf.same(c - 1, d - 1):
            remove_dict[c - 1] += 1
            remove_dict[d - 1] += 1
        
    # friend関係を整理
    for a, b in friend_edge:
        remove_dict[a - 1] += 1
        remove_dict[b - 1] += 1

    # result
    result = []
    for i in range(n):
        target_size = uf.size[uf.find(i)]
        result.append(target_size - remove_dict[i] - 1)

    print(" ".join(map(str, result)))


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.size = [1] * (n)
    def find_root(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    """
    def find_root(self, x):
        root = self.root
        if root[x] == x:
            return x
        else:
            root[x] = self.find_root(root[x])
            return root[x]
    """
    def merge(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)

ab = []
for _ in range(m):
    a, b = map(int, input().split())
    ab.append((a, b))
    uf.merge(a-1, b-1)
cd = []
for _ in range(k):
    c, d = map(int, input().split())
    cd.append((c, d))

#print(uf.root, uf.size)

ans = [uf.size[uf.find_root(i)] - 1 for i in range(n)]

#print(' '.join(map(lambda x: str(x), ans)))
for a, b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1
#print(' '.join(map(lambda x: str(x), ans)))
for c, d in cd:
    #if uf.find_root(uf.root[c-1]) == uf.find_root(uf.root[d-1]):
    if uf.find_root(c-1) == uf.find_root(d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(' '.join(map(lambda x: str(x), ans)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.size = [1] * (n)
    def find_root(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    """
    def find_root(self, x):
        root = self.root
        if root[x] == x:
            return x
        else:
            root[x] = self.find_root(root[x])
            return root[x]
    """
    def merge(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)

ab = []
for _ in range(m):
    a, b = map(int, input().split())
    ab.append((a, b))
    uf.merge(a-1, b-1)
cd = []
for _ in range(k):
    c, d = map(int, input().split())
    cd.append((c, d))

#print(uf.root, uf.size)

ans = [uf.size[uf.find_root(uf.root[i])] - 1 for i in range(n)]

#print(' '.join(map(lambda x: str(x), ans)))
for a, b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1
#print(' '.join(map(lambda x: str(x), ans)))
for c, d in cd:
    if uf.find_root(uf.root[c-1]) == uf.find_root(uf.root[d-1]):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(' '.join(map(lambda x: str(x), ans)))

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

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

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

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans


def main():
    N, M, K = map(int,input().split())
    friend = {}
    block = {}
    tree = UnionFind(N)

    for _ in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        tree.unite(a,b)
        for _ in range(2):
            if not a in friend.keys():
                friend[a] = [b]
            else:
                friend[a].append(b)
            a,b = b,a

    for _ in range(K):
        c,d = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not c in block.keys():
                block[c] = [d]
            else:
                block[c].append(d)
            c,d = d,c

    def solve(x):
        res = 0
        res += tree.get_size(x)

        if x in friend.keys():
            res -= len(friend[x])

        if x in block.keys():
            res -= len(list(filter(lambda y: tree.is_same_group(x,y),block[x])))

        return res - 1

    ans = []
    for i in range(N):
        ans.append(str(solve(i)))

    print(" ".join(ans))


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

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

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):

        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  # 非負なら親ノード，負ならグループの要素数

    def root(self, x):  # root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  # xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y):  # merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  # xの要素数がyの要素数より「小さい」とき入れ替える
            x, y = y, x
        self.parent[x] += self.parent[y]  # xの要素数を更新
        self.parent[y] = x  # yをxにつなぐ
        return True

    def issame(self, x, y):  # same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self, x):  # size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


def do():
    sys.setrecursionlimit(100000000)

    N, M, K = map(int, input().split())
    friends = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    uf1 = UnionFind(N + 1) # 友達候補のUF
    friends_list= [set() for _ in range(N + 1)]
    block_list = [set() for _ in range(N + 1)]

    for query in friends :
        a,b= query
        uf1.merge(a,b)
        friends_list[a].add(b)
        friends_list[b].add(a)

    for query in blocks:
        a, b = query
        block_list[a].add(b)
        block_list[b].add(a)
    anss = []
    for i in range(1,N+1):
        s = uf1.size(i) -1 #ベースの人数

        friends = friends_list[i]
        for friend in friends:
            if uf1.issame(friend,i):
                s -=1

        blocks = block_list[i]
        for block in blocks:
            if uf1.issame(block,i):
                s -=1
        anss.append(s)
    print(*(anss))

if __name__ == "__main__":
    do()

Submission status: Accepted

Solution code:
from bisect import bisect_left


class UnionFind():
    def __init__(self, n):
        self.n = 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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


def check(i, j):
    global friends
    global blocks
    a = bisect_left(friends, [i, j])
    b = bisect_left(friends, [j, i])
    c = bisect_left(blocks, [i, j])
    d = bisect_left(blocks, [j, i])



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

blocks = [[] for _ in range(n)]
friend_num = [0] * n
uf = UnionFind(n)

for _ in range(m):
    array = list(map(int, input().split()))
    uf.unite(array[0]-1, array[1]-1)
    friend_num[array[0]-1] += 1
    friend_num[array[1]-1] += 1

for _ in range(k):
    array = list(map(int, input().split()))
    blocks[array[0]-1].append(array[1]-1)
    blocks[array[1]-1].append(array[0]-1)

for i in range(n):
    uf.find(i)

for i in range(n):
    num = uf.size(i)
    personal_block_list = blocks[i]
    personal_block_num = 0
    for j in personal_block_list:
        if uf.same(i, j):
            personal_block_num += 1

    print(num-friend_num[i]-personal_block_num-1, end=' ')

Submission status: Accepted

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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:
            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

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

ans=[0]*N
uf1=UnionFind(N)
for i in range(M):  # range(m):
    a,b=map(int, input().split()) #a,b:つながっている辺
    uf1.union(a-1,b-1)
    ans[a-1]-=1
    ans[b-1]-=1

for i in range(N):
    uf1.find(i)  # 一周findすることによって接続漏れをなくす。

from collections import defaultdict
ll=defaultdict(int)
for i in uf1.par:
    ll[i]+=1

for i in range(N):
    ans[i]+=ll[uf1.par[i]]-1

for i in range(K):
    a,b=map(int, input().split()) #a,b:つながっている辺
    if uf1.is_same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

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

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

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

n,m,k = map(int, input().split())
uf = UnionFind(n+1)
dd = {}
for i in range(n):
    dd[i] = set()

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

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

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

print(*res)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield set(x for x, _ in group)

N,M,K = m()

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

uni = UnionFind(N-1)

pon = [set() for i in range(N)]

for i in range(M):
    x,y = m()
    po[x-1] -= 1
    po[y-1] -= 1
    uni.unite(x-1,y-1)

for i in range(K):
    x,y = m()
    pon[x-1].add(y-1)
    pon[y-1].add(x-1)

a = list(uni.grouper())


for i in range(len(a)):
    for popo in a[i]:
        po[popo] += len(a[i]) - len(a[i] & pon[popo]) - 1
print(jo(po))

Submission status: Accepted

Solution code:
class Unionfind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N, M, K = map(int,input().split())
deg = [0]*N
uf = Unionfind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)
    #print(uf.d)

for i in range(K):
    a, b = map(int, input().split())
    #to[a] -= 1
    #to[b] -= 1
    if uf.same(a-1, b-1)==True:
        deg[a-1] += 1
        deg[b-1] += 1

for i in range(N):
    #print(i, uf.d[i])
    #print(i, uf.size(i))
    print(uf.size(i)-1-deg[i])

Submission status: Accepted

Solution code:
def d_friend_suggestions():
    N, M, K = [int(i) for i in input().split()]
    Friends = [[int(i) - 1 for i in input().split()] for j in range(M)]
    Blocked = [[int(i) - 1 for i in input().split()] for j in range(K)]

    class UnionFind(object):
        def __init__(self, n):
            """要素番号は 0 スタートを前提とする"""
            self.num_element = n
            self.parents = [-1] * n  # 要素が根の場合は、-(グループの要素数) を格納

        def find(self, x):
            """要素 x が属するグループの根を返す"""
            if self.parents[x] < 0:
                return x
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

        def union(self, x, y):
            """要素 x が属するグループと要素 y が属するグループとを併合する"""
            u, v = self.find(x), self.find(y)

            if u == v:
                return

            # u のグループの方が要素数が少なかった (parents の 定義より)
            if self.parents[u] > self.parents[v]:
                u, v = v, u

            self.parents[u] += self.parents[v]  # u と同グループの要素数を増やす
            self.parents[v] = u  # v は u に繋げる

        def get_size(self, x):
            """要素 x が属するグループの要素数を返す"""
            return -self.parents[self.find(x)]

        def is_same(self, x, y):
            """要素 x, y は同じグループに属するか？"""
            return self.find(x) == self.find(y)

    uf = UnionFind(N)
    degree = [0] * N
    for a, b in Friends:
        uf.union(a, b)
        degree[a] += 1
        degree[b] += 1
    for c, d in Blocked:
        if uf.is_same(c, d):
            degree[c] += 1
            degree[d] += 1

    ans = [uf.get_size(i) - 1 - degree[i] for i in range(N)]
    return ' '.join(map(str, ans))

print(d_friend_suggestions())