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
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:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a - 1].append(b - 1)
    friend[b - 1].append(a - 1)

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

vst = [0] * N
SIZE = []
C = 0
for i in range(N):
    if not vst[i]:
        C += 1
        vst[i] = C
        q = [i]
        cnt = 0
        for u in q:
            cnt += 1
            for v in friend[u]:
                if not vst[v]:
                    vst[v] = C
                    q.append(v)
        SIZE.append(cnt)

for i in range(N):
    ret = SIZE[vst[i] - 1] - 1
    ret -= len(friend[i])
    for b in block[i]:
        if vst[i] == vst[b]:
            ret -= 1
    print(ret, end=' ')
print()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


n,m,k = LI()
ab = [LI() for _ in range(m)]
cd = [LI() for _ in range(k)]

par = [i for i in range(n)]
rank = [0]*n

cnt = [0]*n
cnt2 = [0]*n
for a,b in ab:
    if root(a-1) != root(b-1):
        union(a-1,b-1)
    cnt[a-1] += 1
    cnt[b-1] += 1

for c,d in cd:
    if root(c-1) != root(d-1):
        continue
    cnt2[c-1] += 1
    cnt2[d-1] += 1

f = defaultdict(int)
for i in range(n):
    f[root(i)] += 1

ans = [0]*n
for i in range(n):
    ans[i] = f[root(i)] -1 -cnt2[i] - cnt[i]

print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


class UnionFind:
    __slots__ = ['id','sz']

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

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False


n,m,k = map(int,input().split())
uf=UnionFind(n)
S = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  a-=1;b-=1
  uf.union(a,b)
  S[a].append(b)
  S[b].append(a)
for i in range(k):
  a,b = map(int,input().split())
  a-=1;b-=1
  S[a].append(b)
  S[b].append(a)
ans = [0] * n
for i in range(n):
  tmp = (-uf.id[uf.root(i)])-1
  for vi in S[i]:
    if uf.find(i,vi):
      tmp -= 1
  ans[i] = tmp
print(*ans)

Submission status: Accepted

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


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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = [0] * N
for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    friend[A] += 1
    friend[B] += 1
    uf.unite(A, B)
block = [0] * N
for _ in range(K):
    C, D = map(lambda x: int(x)-1, input().split())
    if uf.same(C, D):
        block[C] += 1
        block[D] += 1
counter = defaultdict(int)
for i in range(N):
    counter[uf.find(i)] += 1
ans = [0] * N
for i in range(N):
    ans[i] = counter[uf.find(i)] - friend[i] - block[i] - 1
print(' '.join(map(str, ans)))

Submission status: Accepted

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

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  #print(x, y)
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
    return sx * sy
    
for a, b in AB:
    merge(a, b)
#print(root)
#print(comp_size)

answer = []
for i in range(N + 1):
    answer.append(comp_size[root_find(i)] - 1)
#print(answer)

for a, b in AB:
    if root_find(a) == root_find(b):
        answer[a] -= 1
        answer[b] -= 1
for c, d in CD:
    if root_find(c) == root_find(d):
        answer[c] -= 1
        answer[d] -= 1
print(*answer[1:])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M,K=MI()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    friend_cnt = [0]*N
    ans = [0]*N
    for _ in range(M):
        a,b = MI_()
        unite(a,b)
        friend_cnt[a]+=1
        friend_cnt[b]+=1
    for i in range(N):
        ans[i] = -nodes[get_root(i)]-1-friend_cnt[i]
    for _ in range(K):
        a,b = MI_()    
        if get_root(a)==get_root(b):
            ans[a]-=1
            ans[b]-=1
    print(*ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

#Union Find

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

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n
lst2 = [0]*n
lst3 = [0]*n
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    lst2[a] += 1
    lst2[b] += 1
    unite(a,b)

block = 0

for i in range(k):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    if same(a,b):
        lst3[a] += 1
        lst3[b] += 1

ans = [0]*n

for i in range(n):
    res = size(i) -1
    res -= lst2[i]+lst3[i]
    ans[i] = res


print(*ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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())
U = UnionFind(N)
res = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    res[a - 1] -= 1
    res[b - 1] -= 1
    U.union(a - 1, b - 1)


for _ in range(K):
    c, d = map(int, input().split())
    if U.same(c - 1, d - 1):
        res[c - 1] -= 1
        res[d - 1] -= 1
for i in range(N):
    res[i] += U.size(i) - 1
print(" ".join(map(str, res)))

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]
CD = [list(map(int,input().split())) for _ in [0]*K]

import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self,N):
        self.Parent = list(range(N))
    def get_Parent(self,n):
        if self.Parent[n] == n:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
E_f = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    U.merge(a,b)
    E_f[a].append(b)
    E_f[b].append(a)
group = [set() for _ in [0]*N]
for i in range(N):
    p = U.get_Parent(i)
    group[p].add(i)

E_b = [[] for _ in [0]*N]
for c,d in CD:
    c -= 1
    d -= 1
    E_b[c].append(d)
    E_b[d].append(c)

ans = [0]*N
for i in range(N):
    p = U.get_Parent(i)
    cnt = 0
    for b in E_b[i]:
        if b in group[p]: cnt += 1
    ans[i] = len(group[p]) -cnt - len(E_f[i]) - 1

print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

################
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    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 main():
    mod=10**9+7
    N,M,K=MI()
    uf = UnionFind(N)
    cnt=[0]*N#友達の数
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        cnt[a]+=1
        cnt[b]+=1
        uf.union(a,b)
        
    blo=[0]*N#同じユニオン内でブロックしているかず
    for i in range(K):
        c,d=MI()
        c-=1
        d-=1
        if uf.same(c,d):
            blo[c]+=1
            blo[d]+=1
    ans=[0]*N    
    for i in range(N):
        ans[i]=uf.size(i) - cnt[i]-blo[i]-1
        
    print(' '.join(map(str, ans)))
        
    

main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    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 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


N, M, K = map(int, input().split())
uf = UnionFind(N)
count_friends = [1] * N
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  count_friends[a-1] += 1
  count_friends[b-1] += 1


parents = [uf.find(i) for i in range(N)]
par_dict = {}
for p in parents:
  if p in par_dict:
    par_dict[p] += 1
  else:
    par_dict[p] = 1

count_block = [0] * N
for i in range(K):
  c, d = map(int, input().split())
  if parents[c-1] == parents[d-1]:
    count_block[c-1] += 1
    count_block[d-1] += 1

ans = [-1]*N
for i in range(N):
  p = parents[i]
  ans[i] = par_dict[p] - count_friends[i] - count_block[i]

print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

#Union Find
class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # x と y の集合を結合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    # x が属する集合の要素数を返す
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

N,M,K = LI()
A,B = LIR(M,2)
C,D = LIR(K,2)

b = defaultdict(set)
t = defaultdict(set)

uf = UF(N)

for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    t[A[i]-1].add(B[i]-1)
    t[B[i]-1].add(A[i]-1)

num = [0]*N
for i in range(K):
    if uf.is_same(C[i]-1, D[i]-1):
        num[C[i]-1] -= 1
        num[D[i]-1] -= 1

ans = []
for i in range(N):
    ans.append(uf.get_size(i)-1-len(t[i])+num[i])
print(*ans)

Submission status: Accepted

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

e_list = [[] for i in range(N)]

b_list = [[] for i in range(N)]

edge1 = []
edge2 = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge1.append((a,b))
    e_list[a].append(b)
    e_list[b].append(a)

for i in range(K):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge2.append((a,b))
    b_list[a].append(b)
    b_list[b].append(a)

color = [-1]*N

from collections import deque

def BFS(vi,c):
    Q = deque([vi])
    color[vi]=c
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color[v1]==-1:
                color[v1]=c
                Q.appendleft(v1)

c=0

for i in range(N):
    if color[i]==-1:
        BFS(i,c)
        c+=1

member = [0]*(max(color)+1)

for i in range(N):
    member[color[i]]+=1
#rint(member)
ans = []
for i in range(N):
    a = member[color[i]] -1 - len(e_list[i]) 
    for j in range(len(b_list[i])):
        if color[i]==color[b_list[i][j]]:
            a-=1

    ans.append(a)

print(*ans)

"""
good = [0]*(max(color)+1)
bad = [0]*(max(color)+1)
for i in range(M):
    good[color[edge1[i][0]]]+=1

for i in range(K):
    bad[color[edge2[i][0]]]+=1

ans = 0
for i in range(len(member)):
    ans += (member[i]*(member[i]-1))//2 - good[i] - bad[i]

print(ans)
"""

Submission status: Accepted

Solution code:
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

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

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

    # 併合
    def 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_check(self, x, y):
        return self.find(x) == self.find(y)

    def update_all(self):
        n = len(self.par)
        for i in range(n):
            self.par[i] = self.find(i)

def main():
    n, m, k = getList()
    friends = [[] for i in range(n)]
    blocks = [[] for i in range(n)]

    uf = UnionFind(n)

    for i in range(m):
        a, b = getList()
        uf.union(a-1, b-1)
        friends[a-1].append(b-1)
        friends[b-1].append(a-1)

    for i in range(k):
        a, b = getList()
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)
    uf.update_all()
    # print(uf.par)?
    ans = []
    for i in range(n):
        tmp = uf.size[uf.par[i]]
        for fr in friends[i]:
            if uf.same_check(i, fr):
                tmp -= 1
        for bl in blocks[i]:
            if uf.same_check(i, bl):
                tmp -= 1

        ans.append(tmp-1)

    print(*ans)


if __name__ == "__main__":
    main()

"""
10
203941992 742164984
670850202 743524472
687298546 744891559
676493045 744182895
385467254 742631752
740505911 744926772
425723256 743348462
225362543 742332848
399450535 742706299
563528474 743419738
"""

Submission status: Accepted

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

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

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

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

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

friend=[0 for i in range(n+1)]
blocked={i:[] for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    friend[a]+=1
    friend[b]+=1
    A.union(a,b)
    
    
for j in range(k):
    x,y=map(int,input().split())
    
    blocked[x].append(y)
    blocked[y].append(x)
    
for i in range(1,n+1):
    A.find(i)
    
parent=A.par

howmany={i:0 for i in range(n+1)}

for i in range(1,n+1):
    x=parent[i]
    howmany[parent[i]]+=1
    
#howmanyに同じグループが何個あるか

lists=[]
for i in range(1,n+1):
    sums=howmany[parent[i]]-1-friend[i]
    for some in blocked[i]:
        if parent[i]==parent[some]:
            sums-=1
    lists.append(sums)
print(*lists)

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]
N, M, K = map(int, input().split())
frend = defaultdict(list)
F = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  frend[a] += [b]
  frend[b] += [a]
  F.unit(a-1,b-1)
ans = [0]*N
for i in range(N):
  p = F.find(i)
  X = F.count(p)
  ans[i] = X-len(frend[i+1])-1
for i in range(K):
  a, b = map(int, input().split())
  if F.same(a-1,b-1):
    ans[a-1] -= 1
    ans[b-1] -= 1

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索する過程で親を更新
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        if UnionFind.same_check(self,x,y):
            return
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

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

ans = [u.size(i)-friend[i] for i in range(n)]
#print(*ans)
for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)