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 sys
input = sys.stdin.readline
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_
N, K, L = map(int, input().split())
node_list1 = [UnionFindNode(i) for i in range(N)]
d3 = [0] * N
for _ in range(K):
    a, b = map(int, input().split())
    node_list1[a-1].unite(node_list1[b-1])
    d3[a-1] += 1
    d3[b-1] += 1
    
for _ in range(L):
    a, b = map(int, input().split())
    if node_list1[a-1].root().group_id_ == node_list1[b-1].root().group_id_:
        d3[a-1] += 1
        d3[b-1] += 1


rr = []
for i in range(N):
    x = node_list1[i].root().member_num_
    rr.append(x-d3[i]-1)
print(*rr)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

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


def solve():
    return


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]

def read_int():
    return int(sys.stdin.readline())

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    n, m, k = read_int_list()
    potential_friends = UnionFind(n)
    count_friends = [0] * n
    count_blocking_in_potential_friends = [0] * n

    for _ in range(0, m):
        a, b = [p - 1 for p in read_int_list()]
        potential_friends.union(a, b)
        count_friends[a] += 1
        count_friends[b] += 1
    for _ in range(0, k):
        c, d = [p - 1 for p in read_int_list()]
        if potential_friends.same(c, d):
            count_blocking_in_potential_friends[c] += 1
            count_blocking_in_potential_friends[d] += 1
    
    ans = []
    for i in range(0, n):
        ans.append(str(potential_friends.size(i) - 1 - count_friends[i] - count_blocking_in_potential_friends[i]))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict


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

    def find(self, x):
        """
        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 と 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 is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

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


def main():
    N, M, K = [int(x) for x in input().split()]

    uf = UnionFind(N)
    fcount = defaultdict(int)
    for _ in range(M):
        A, B = [int(x) for x in input().split()]
        uf.union(A-1, B-1)
        fcount[A-1]+=1
        fcount[B-1]+=1

    import collections
    bcount = defaultdict(int)
    for _ in range(K):
        C, D = [int(x) for x in input().split()]
        C-=1
        D-=1
        if uf.is_same(C, D):
            bcount[C]+=1
            bcount[D]+=1

    groups = collections.defaultdict(set)
    for i in range(N):
        groups[uf.find(i)].add(i)

    counts = []
    for i in range(N):
        friends = groups[uf.find(i)]
        cnt = len(friends)-1-fcount[i]-bcount[i]
        counts.append(cnt)
    print(" ".join(map(str, counts)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


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+1)
start = [0] * (N+1)

friend = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)
    start[a] -= 1
    start[b] -= 1


block = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c, d):
        start[c] -= 1
        start[d] -= 1

for i in range(1, N+1):
    ans = uf.size(i)-1 + start[i]
    print(ans, end=" ")

print("")

Submission status: Accepted

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

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

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

uf = UnionFind(n)
f = [0 for i in range(n)]
ans = []

for a, b in ab:
    uf.union(a-1, b-1)
    f[a-1] += 1
    f[b-1] += 1

for i in range(n):
    ans.append(-uf.parents[uf.find(i)]-f[i] - 1)

for c,d in cd:
    if uf.find(c-1) == uf.find(d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(" ".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

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

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

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

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

        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

n, m, k = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
friends = [set() for _ in range(n)]
DS = DisjointSet(n)
for _ in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    friends[a].add(b)
    friends[b].add(a)
    if not DS.has_same_root(a, b):
        DS.unite(a, b)

h_cnt = [0] * n
hostiles = [set() for _ in range(n)]
for _ in range(k):
    c, d = [int(item) for item in input().split()]
    c -= 1; d -= 1 
    hostiles[c].add(d)
    hostiles[d].add(c)

visited = [0] * n
def dfs(par, p, v):
    queue = deque()
    queue.append((p, v))
    visited[v] = True
    while queue:
        p, v = queue.popleft()
        for h in hostiles[v]:
            if h not in friends[v] and DS.has_same_root(h, v):
                h_cnt[v] += 1
        for nv in edge[v]:
            if visited[nv]:
                continue
            if nv == p:
                continue
            queue.append((v, nv))
            visited[nv] = True

for i in range(n):
    if visited[i]:
        continue
    visited[i] = True
    dfs(i, -1, i)

ans = []
for i in range(n):
    ans.append(DS.get_size(i) - 1 - h_cnt[i] - len(edge[i]))
    
print(*ans)

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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,k = inpm()
    uf = UnionFind(n)
    ok = [0 for _ in range(n)]
    block = []
    for _ in range(m):
        a,b = inpm()
        uf.union(a-1,b-1)
        ok[a-1] += 1
        ok[b-1] += 1
    for _ in range(k):
        c,d = inpm()
        block.append((c-1,d-1))
    ans = [-1 for _ in range(n)]
    for i in range(len(block)):
        [x,y] = block[i]
        if uf.same(x,y):
            ans[x] -= 1
            ans[y] -= 1
    for i in range(n):
        ans[i] += uf.size(i)-ok[i]
    print(*ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

n,m,k=map(int,input().split())
twi=UnionFind(n)
ans=[-1 for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    twi.Unite(a,b)
    ans[a]-=1
    ans[b]-=1

for i in range(1,n+1):
    ans[i]+=twi.Count(i)

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

for i in range(1,n):
    print(ans[i],end=" ")
print(ans[n])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        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]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            # グループ0の分を引いて返却
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M, K = MAP()
uf = UnionFind(N)
ans = [0] * N
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
for a in range(N):
    ans[a] += uf.get_size(a) - 1
for i in range(K):
    a, b = MAP()
    a -= 1; b -= 1
    if uf.is_same(a, b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)

Submission status: Accepted

Solution code:
import sys

class UFT(): #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    parent = UFT(N)
    NG = [0] * N
    Connected = [0] * N
    treeSize = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        parent.unite(x-1, y-1)
        Connected[x-1] += 1
        Connected[y-1] += 1
    for _ in range(K):
        x, y = map(int, input().split())
        if parent.find(x-1) != parent.find(y-1): continue
        parent.unite(x-1, y-1)
        NG[x-1] += 1
        NG[y-1] += 1
    for i in range(N):
        key = parent.find(i)
        if key in treeSize: treeSize[key] += 1
        else: treeSize[key] = 1
    Ans = [0] * N
    for i in range(N):
        Ans[i] = treeSize[parent.find(i)] - Connected[i] - NG[i] - 1
    print(" ".join(map(str, Ans)))

    return 0

if __name__ =="__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M, K = [int(x) for x in input().strip().split()]

# 友達グループ(候補含む)
par = [i for i in range(N+1)]
rank = [0] * (N+1)

# 友達
friends = [0 for _ in range(N+1)]

# ブロックしている数
blocked = [0 for _ in range(N+1)]

def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]

def isSame(x, y):
    return find(x) == find(y)

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 

    if rank[x] >= rank[y]:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        par[x] = y

for m in range(M):
    a, b = [int(x) for x in input().strip().split()]
    union(a, b)
    friends[a] += 1
    friends[b] += 1

for k in range(K):
    c, d = [int(x) for x in input().strip().split()]
    if isSame(c, d):
        blocked[c] += 1
        blocked[d] += 1


for n in range(1, N+1):
    find(n)

cnt = Counter(par)
print(*[cnt[par[n]] - friends[n] - blocked[n] - 1 for n in range(1, N+1)])

Submission status: Accepted

Solution code:
from collections import deque

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

friend = [[] for i in range(N)]
ans = [0] * N ###友達関係にある人は必ず同グループにいるので, あらかじめマイナスにしておく

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

block = []

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

group = [0] * N
count = 1

for i in range(N):
    if group[i] == 0:
        group[i] = count
        stack = deque()
        stack.append([i,i])
        while stack:
            x = stack.pop()
            for y in friend[x[1]]:
                if y == x[0] or group[y] == count:
                    continue
                group[y] = count
                stack.append([x[1],y])
            #print(stack)
        count += 1

###ブロック関係かつ同グループに入っている二人にマイナスポイントをつける
for x in block:
    if group[x[0]] == group[x[1]]:
        ans[x[0]] -= 1
        ans[x[1]] -= 1

num = [0] * count###各グループの人数

for i in range(N):
    num[group[i]] += 1

for i in range(N):
    ans[i] += num[group[i]] - 1###-1は自分

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

Submission status: Accepted

Solution code:
from collections import deque, Counter

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

def dfs(s, c):
    """
    s: node
    c: number
    """

    q = deque()
    q.append(s)
    visited[s] = True
    color[s] = c
    
    while q:
        u = q.pop()
        for v in graph[u]:
            if visited[v]:
                continue
                
            visited[v] = True
            color[v] = c
            q.append(v)


graph = [[] for _ in range(N)]
for a, b in AB:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

visited = [False] * N
color = [-1] * N
c = 0

for i in range(N):
    if not visited[i]:
        dfs(i, c)
        c += 1
        
ctr = Counter(color)

block = [[] for _ in range(N)]
for c, d in CD:
    if color[c - 1] == color[d - 1]:
        block[c - 1].append(d - 1)
        block[d - 1].append(c - 1)

ans = [0] * N
for i in range(N):
    ans[i] = ctr[color[i]] - 1 - len(graph[i]) - len(block[i])
    
print(*ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
fri=[0 for _ in range(n)]
blo=[0 for _ in range(n)]

par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]
 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    merge(a,b)
    fri[a]+=1
    fri[b]+=1
    
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if same(c,d):
        blo[c]+=1
        blo[d]+=1

ans=[size[find(i)]-fri[i]-blo[i]-1 for i in range(n)]
print(*ans)

Submission status: Accepted

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

class UF():
  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 size(self, x):
    return self._size[self.find_root(x)]

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

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

cf=[[] for i in range(n)]
cb=[[] for i in range(n)]

UFa=UF(n)
UFb=UF(n)
for i in range(m):
  x,y=map(int,input().split())
  UFa.unite(x-1,y-1)
  UFb.unite(x-1,y-1)
  cf[x-1].append(y-1)
  cf[y-1].append(x-1)
UFa.groupnum()

for i in range(k):
  x,y=map(int,input().split())
  cb[x-1].append(y-1)
  cb[y-1].append(x-1)

ans=[]
for i in range(n):
  x=(UFa.size(i)-1)-len(cf[i])
  for j in range(len(cb[i])):
    if UFa.samegroup(i,cb[i][j]):
      x-=1
  ans.append(str(x))
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点

n, m, k = map(int, input().split())
par = [-1]*n
f = [set() for _ in range(n)]
b = [set() for _ in range(n)]
for _ in range(m):
    a, _b = map(int, input().split())
    f[a-1].add(_b-1)
    f[_b-1].add(a-1)
    unite(a-1, _b-1)
for _ in range(k):
    a, _b = map(int, input().split())
    b[a-1].add(_b-1)
    b[_b-1].add(a-1)

for i in range(n):
    ans = size(i)-len(f[i])-1
    for node in b[i]-f[i]:
        if same(i, node):
            ans -= 1
    print(ans, end=" " if i!=n-1 else "\n")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# solution
N,M,K=list(map(int,input().split()))
group=UnionFind(N)
friend=defaultdict(int)
for _ in range(M):
    src,dst=list(map(int,input().split()))
    group.Unite(src-1,dst-1)
    friend[src-1]+=1
    friend[dst-1]+=1

block=defaultdict(list)
for _ in range(K):
    src,dst=list(map(int,input().split()))
    block[src-1].append(dst-1)
    block[dst-1].append(src-1)

ans=[]
for i in range(N):
    total=group.Count(i)
    num=total-1-friend[i]
    #remove block
    for b in block[i]:
        if group.isSameGroup(i,b):
            num-=1
    ans.append(num)

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