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
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # 初期化（初期状態は全要素が根）
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す O(log 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]

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

        # 根が同じならx,yは既に同じグループ
        if x == y:
            return

        # xとyのサイズを比較し、xのほうが小さい場合はx,yをswapする
        # ※unionは大きい方のグループに小さい方のグループを引っ付けるため。
        # ※負の数なので不等号の向きに注意
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        # xにyをくっつける
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用
    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int,input().split())
ab = []
cd = []

# 友達関係
frineds = [0] * n
# ブロック関係
block = [0] * n

for i in range(m):
    ab.append(list(map(int,input().split())))
    frineds[ab[i][0]-1] += 1
    frineds[ab[i][1]-1] += 1

# Union Find 初期化
uf = UnionFind(n)
# 友達関係をもとにUniteする
for _ab in ab:
    uf.union(_ab[0]-1, _ab[1]-1)

for i in range(k):
    cd.append(list(map(int,input().split())))
    
    # 同じグループ内の場合
    if uf.same(cd[i][0]-1, cd[i][1]-1):
        block[cd[i][0]-1] += 1
        block[cd[i][1]-1] += 1

for i in range(n):
    ans = uf.size(i) - 1 - frineds[i] - block[i]
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind:#
    def __init__(self,N):#親のリスト、ランク(部分木の高さ)の初期化
        self.parent=[i for i in range(N)]
        self.rank=[0]*N
    def root(self,a):#根を返す
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):#同じ木に属するか(根が同じか)
        return self.root(a)==self.root(b)
    def unite(self,a,b):#木をつなげる
        ra=self.root(a)
        rb=self.root(b)
        if ra==rb:
            return
        if self.rank[ra]<self.rank[rb]:
            self.parent[ra]=rb
        else:
            self.parent[rb]=ra
            if self.rank[ra]==self.rank[rb]:
                self.rank[ra]+=1
N,M,K=map(int,input().split())
uf=UnionFind(N)
lfriend=[0 for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(a-1,b-1)
    lfriend[a-1]+=1
    lfriend[b-1]+=1
lnfam=[0 for i in range(N)]
for i in range(N):
    rt=uf.root(i)
    lnfam[rt]+=1
lnblock=[0 for i in range(N)]
for i in range(K):
    c,d=map(int,input().split())
    if uf.root(c-1)==uf.root(d-1):
        lnblock[c-1]+=1
        lnblock[d-1]+=1
for i in range(N):
    print(lnfam[uf.root(i)]-lfriend[i]-lnblock[i]-1,end=" ")
print()
#print("lfriend",lfriend)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
parent=list(range(n))
rank=[0]*n
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
f_b=[0]*n
for i in range(m):
	a,b=map(int,input().split())
	unite(a-1,b-1)
	f_b[a-1]+=1
	f_b[b-1]+=1
for j in range(k):
	c,d=map(int,input().split())
	if root(c-1)==root(d-1):
		f_b[c-1]+=1
		f_b[d-1]+=1
p=[0]*n
ans=[]
for i in range(n):
	p[root(i)-1]+=1
for i in range(n):
	r=p[root(i)-1]-f_b[i]-1
	ans.append(r)
print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

class union_find:
    def __init__(self, n):
        self.N = n
        self._parent = [i for i in range(self.N)]
        self._mem = [1] * self.N
        self.compo = self.N

    def parent(self, a):
        if self._parent[a] == a:
            return a
        self._parent[a] = self.parent(self._parent[a])
        return self._parent[a]

    def united(self,a, b):
        return self.parent(a) == self.parent(b)
    
    def unite(self,a, b):
        a = self.parent(a)
        b = self.parent(b)
        if(a == b): return False
        if self._mem[a] > self._mem[b]: a, b = b, a
        self._parent[a] = b
        self._mem[b] += self._mem[a]
        self.compo -= 1
        return True
    
    def is_root(self,a):
        return a == self._parent[a]
    def mem_cnt(self,a):
        return self._mem[self.parent(a)]
    def dump(self):
        print(self._parent)
    

def main():
    N, M, K = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
    C = [0] * K
    D = [0] * K
    for i in range(K):
        C[i], D[i] = rip()

    uf = union_find(N)
    for i in range(M):
        uf.unite(A[i] - 1, B[i] - 1)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.mem_cnt(i) - 1
    for i in range(K):
        if uf.united(C[i] - 1, D[i] - 1):
            ans[C[i] - 1] -= 1
            ans[D[i] - 1] -= 1
    for i in range(M):
        ans[A[i] - 1] -= 1
        ans[B[i] - 1] -= 1

    print(" ".join([str(n) for n in ans]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,M,K = map(int,input().split())
    friend = [[] 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)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

    def member(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.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_member(self):
        return {r:self.member(r) for r in self.roots()}

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

def main():
    N,M,K = map(int,input().split())
    adj = [[] for _ in range(N)]
    ans = [None]*N
    uf = UnionFind(N)
    for i in range(M+K):
        a,b = map(lambda x : int(x)-1,input().split())
        if i < M:
            uf.unite(a,b)
            adj[a].append(b)
            adj[b].append(a)
        elif uf.same(a,b):
            adj[a].append(b)
            adj[b].append(a)
    for i in range(N):
        ans[i] = uf.size(i) - len(adj[i]) - 1
    print(*ans,sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

    def member(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.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_member(self):
        return {r:self.member(r) for r in self.roots()}

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

def main():
    N,M,K = map(int,input().split())
    adj = [[] for _ in range(N)]
    ans = [None]*N
    uf = UnionFind(N)
    for i in range(M+K):
        a,b = map(int,input().split())
        if i < M:
            uf.unite(a-1,b-1)
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
        elif uf.same(a-1,b-1):
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
    for i in range(N):
        ans[i] = uf.size(i) - len(adj[i]) - 1
    print(*ans,sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
linkList = []
ans = [0] *(N+1)
visited = [0] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    linkList.append(link)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Accepted

Solution code:
class UnionFind():
    """Union Find実装"""

    def __init__(self, n):
        """要素数nで初期化する"""
        self.n = n

        # rootノードでその木の要素数を記録する
        # root[x]<0ならそのノードが根かつその値が木の要素数
        self.root = [-1]*(n+1)
        
        # 木の高さを記録
        # Union時に高さの低い木を高い木にくっつける
        self.rank = [0]*(n+1)

    def find(self, x):
        """ノードXのルートノードを返す"""

        # root[x]<0ならそのノードが根かつその値が木の要素数
        if (self.root[x] < 0):
            return x
        
        # 経路圧縮しながらルートノードを見つける
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        """ノードxの属するツリーとノードyの属するツリーをくっつける"""
        
        # ルートノードを見つける
        x = self.find(x)
        y = self.find(y)

        # 同じ木の場合は何もしない
        if (x == y):
            return

        # 違う木の場合は木のたかさrankを見てくっつける木を選ぶ 
        # 高さが同じ場合はxをyにくっつける
        if (self.rank[x] > self.rank[y]):
            # 要素数を足す
            self.root[x] += self.root[y]
            # 木をくっつける
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            # rankが同じ場合は１増やす
            if (self.rank[x] == self.rank[y]): self.rank[y] += 1

    def same(self, x, y):
        """xとyが同じ木に属するかどうか判定する"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """xが属する木のノード数を返す"""
        return -self.root[self.find(x)]
        
N, M, K = map(int, input().split())
uf = UnionFind(N)
blocks = [[] for i in range(N+1)]
friends = [0] * (N+1)

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

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

ans = [0] * N
for i in range(1, N+1):
    block_num = 0
    for b in blocks[i]:
        if uf.same(i, b):
            block_num += 1
    ans[i-1] = uf.count(i) - block_num - friends[i] - 1

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

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=x
 if(x==y)+(m>0):s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
i=-1
for a,b in t:
 x,y=sorted((r(a),r(b)));i+=1
 if(x!=y)*m>i:p[x]+=p[y];p[y]=x
 if(x!=y)*i<m:s[a]-=1;s[b]-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>i:p[x]+=p[y];p[y]=x
 if(x!=y)*i<m:s[a]-=1;s[b]-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=sorted((r(a),r(b)))
  if(x!=y)*m>i:
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if x==y or i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if r(a)==r(b)or i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,s=[-1]*-~n,[-1]*-~n
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  s[a]-=1
  s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
for c,d in t[m:]:
  if r(c)==r(d):
    s[c]-=1
    s[d]-=1
print(*s[1:])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,f=[-1]*-~n,[-1]*-~n
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  f[a]-=1
  f[b]-=1
a=[f[i]-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
f=[[]for _ in p]
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  f[a]+=b,
  f[b]+=a,
a=[~len(f[i])-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

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

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1

n, m, k = LI()
U = UnionFind(n)
AB = LIR(m)
for a, b in AB:
    U.union(a - 1, b - 1)

ans = [U.get_size(U.root(i)) - 1 for i in range(n)]
for a, b in AB:
    ans[a - 1] -= 1
    ans[b - 1] -= 1

for _ in range(k):
    c, d = LI()
    if U.is_same(c - 1, d - 1):
        ans[c - 1] -= 1
        ans[d - 1] -= 1


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)

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

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
cd=[list(map(int,input().split()))for i in range(k)]
#UnionFind木
class UnionFind():
    #作りたい要素数nで初期化
    #使用するインスタンス変数の初期化
    def __init__(self,n):
        #ルートノード
        #n[x]<0ならそのノードが根かつその値の絶対値が木の要素数
        #ルートノードでその木の要素数を記録する
        self.root=[-1]*n
        #木をくっつける時にアンバランスにならないように調整する
        self.rnk=[0]*n
    #ノードxのルートノードを見つける
    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            #ここで代入しておくことで、のちの繰り返しを避ける
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]
    #木の併合、入力は併合したい各ノード
    def Unite(self,x,y):
        #入力ノードのルートノードを見つける
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        #すでに同じ木に属していた場合
        if x==y:
            return
        #違う木に属していた場合rを見てくっける方法を決める
        #木の高さを見て低いほうを高い木に結合する
        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が同じ（深さに差がない場合)はrnkを1増やす
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1
    #xとyが同じグループに属するか判断
    def Root_Same(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)
    #ノードxが属する木のサイズを返す
    def Count(self,x):
        return -self.root[self.Find_Root(x)]
#UnionFindクラスを作成
u=UnionFind(n)
#友達関係のa,bの木を接合する
for a,b in ab:
    #配列のインデックスだからa-1,b-1とする
    u.Unite(a-1,b-1)
#同じグループに属する人-自分自身の値をansに格納する
ans=[u.Count(i)-1 for i in range(n)]
#(友達候補)=(同じグループに属する人の数)-(友達人数)-(ブロック人数)-(自分自身)
#まず友達人数を引く
for a,b in ab:
    #if文は省略しても可
    if u.Root_Same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
#最後にブロック人数を引く
for c,d in cd:
    #同じグループに属するならば引く
    if u.Root_Same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.height = [1] * n
        self.size = [1] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.height[x] < self.height[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.height[x] == self.height[y]:
                    self.height[x] += 1

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
exc = [set() for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    exc[a - 1].add(b - 1)
    exc[b - 1].add(a - 1)
    uf.unite(a - 1, b - 1)
for _ in range(K):
    c, d = map(int, input().split())
    if uf.issame(c - 1, d - 1):
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [uf.group_size(i) - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
cd=[list(map(int,input().split()))for i in range(k)]
class UnionFind():
    def __init__(self,n):
        self.n=[-1]*n
        self.r=[0]*n
    def Find_Root(self,x):
        if self.n[x]<0:
            return x
        else:
            self.n[x]=self.Find_Root(self.n[x])
            return self.n[x]
    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.r[x]>self.r[y]:
            self.n[x]+=self.n[y]
            self.n[y]=x
        else:
            self.n[y]+=self.n[x]
            self.n[x]=y
            if self.r[x]==self.r[y]:
                self.r[y]+=1
    def Root_Same(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)
    def Count(self,x):
        return -self.n[self.Find_Root(x)]
u=UnionFind(n)
for a,b in ab:
    u.Unite(a-1,b-1)
ans=[u.Count(i)-1 for i in range(n)]
for a,b in ab:
    if u.Root_Same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
for c,d in cd:
    if u.Root_Same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)