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:
from collections import defaultdict


def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


# x,yの属する集合の併合
def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def same(x, y):
    return find_root(x) == find_root(y)


def group_size(x):
    return size[find_root(x)]


dic1 = defaultdict(list)
dic2 = defaultdict(list)

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


parent = [i for i in range(n)]  # 根
rank = [1] * n  # 深さ
size = [1] * n  # iを根とするグループのサイズ

edge = [[ab[m - 1 - i][0] - 1, ab[m - 1 - i][1] - 1] for i in range(m)]

res = []
for i in range(m):
    a = find_root(edge[i][0])
    b = find_root(edge[i][1])
    if a == b:
        res.append(0)
    else:
        res.append(size[a] * size[b])
        unite(a, b)


for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    dic1[a].append(b)
    dic1[b].append(a)
for i in range(k):
    c = cd[i][0] - 1
    d = cd[i][1] - 1
    if same(c, d):
        dic2[c].append(d)
        dic2[d].append(c)

ans = []
for i in range(n):
    ans.append(group_size(i)-1 - len(dic1[i]) - len(dic2[i]))
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    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()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 
N, M, K = MAP()
F = [LIST() for i in range(M)]
B = [LIST() for i in range(K)]

friends = defaultdict(list)
tree = UnionFind(N)
for a, b in F:
    tree.union(a-1, b-1)
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)

blocks = defaultdict(list)
for a, b in B:
    blocks[a-1].append(b-1)
    blocks[b-1].append(a-1)

for i in range(N):
    m = 0
    for b in blocks[i]:
        if tree.same(i, b):
            m += 1
    print(tree.size(i)-len(friends[i])-1-m, end=" ")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

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


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

    u = UnionFind(N)
    ans1 = [0] * N
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        ans1[a - 1] += 1
        ans1[b - 1] += 1
        u.union(a - 1, b - 1)

    ans2 = [0] * N
    for _ in range(K):
        a, b = [int(x) for x in input().split()]
        if u.same(a - 1, b - 1):
            ans2[a - 1] += 1
            ans2[b - 1] += 1

    for i in range(N):
        print(u.size(i) - ans1[i] - ans2[i] - 1, end=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
total=0
def bfs(ind,num):
    kouho=friends[ind]
    
    for i in kouho:
        if sans[i]!=-1:
            continue
        num+=1
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        num+=bfs(i,0)
    return num
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
total=bfs(0,total)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    total=bfs(i,total)
ans=[0 for _ in range(n)]


for i in range(n):
    l[i]=set(l[i])


for i in range(n):
    tmp=l[sans[i]]
    ans[i]+=len(tmp)-len(friends[i])-1
    for j in block[i]:
        if sans[i]==sans[j]:
            ans[j]-=1

ans=" ".join(map(str,ans))
#print("total:",total)
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
input=sys.stdin.readline
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)]
num = [0]*(n+1)
g = [[] for i in range(n+1)]
uf = UnionFind(n+1)
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  uf.union(a,b)
for c,d in cd:
  if uf.same(c,d) == True:
    g[c].append(d)
    g[d].append(c)
for i in range(1,n+1):
  print(uf.size(i)-len(g[i])-1,end=" ")

Submission status: Accepted

Solution code:
from collections import deque
n,m,k = map(int, input().split())
a = [list(map(lambda x:int(x)-1, input().split())) for i in range(m)]
c = [list(map(lambda x:int(x)-1, input().split())) for i in range(k)]

mp=[set() for _ in range(n)]
bl=[set() for _ in range(n)]

for af, bf in a:
    mp[af].add(bf)
    mp[bf].add(af)

for cf,df in c:
    bl[cf].add(df)
    bl[df].add(cf)

sz=[0]*n
for i in range(n):
    if sz[i]>0:
        continue

    d=deque()
    reach={i}
    d.append(i)
    while d:
        s=d.pop()
        for g in mp[s]:
            if g in reach:
                continue
            else:
                reach.add(g)
                d.append(g)

    for j in reach:
        sz[j]=len(reach)

    for k in reach:
        for j in bl[k]:
            if j in reach:
                sz[k]-=1

for i in range(n):
    sz[i]-=len(mp[i])+1

print(*sz)

Submission status: Accepted

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

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

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

    def count(self, x):
        return -self.root[self.get_root(x)]

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

        if x == y:
            return
        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
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1


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

f = UnionFind(N + 1)

friends = {}
for _ in range(M):
    a, b = map(int, input().split())
    if friends.get(a) is None:
        friends[a] = set([b])
    else:
        friends[a].add(b)
    if friends.get(b) is None:
        friends[b] = set([a])
    else:
        friends[b].add(a)
    f.unite(a, b)

blocks = {}
for _ in range(K):
    c, d = map(int, input().split())
    if blocks.get(c) is None:
        blocks[c] = set([d])
    else:
        blocks[c].add(d)
    if blocks.get(d) is None:
        blocks[d] = set([c])
    else:
        blocks[d].add(c)


def get_number_of_blocks_in_same_group(i):
    block = blocks.get(i, [])
    return len([j for j in block if f.is_same_group(i, j)])


for i in range(1, N + 1):
    count = f.count(i)
    friend = friends.get(i, [])
    num_friends = len(friend)
    num_blocks = get_number_of_blocks_in_same_group(i)
    ans = count - num_friends - num_blocks - 1
    # print('count', count, friend, num_friends, num_blocks)
    print(ans)

Submission status: Accepted

Solution code:
#頂点xの親を求める
def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

#頂点aと頂点bのグループをつなげる
def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

#N個の頂点、M本の道で、i個目の道がAi-Biとなるような
#グラフについてグループ化する
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)]
parent=[-1]*(N+1)
for A,B in AB:
    connect(A,B)
ans=[0]*(N+1)
for i in range(1,N+1):
    ans[i]=-parent[find_parent(i)]-1
for A,B in AB:
    ans[A]-=1
    ans[B]-=1
for C,D in CD:
    if find_parent(C)==find_parent(D):
        ans[C]-=1
        ans[D]-=1
print(*ans[1:])

Submission status: Accepted

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
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())
f=[set() for i in range(n)]
h=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    f[a].add(b)
    f[b].add(a)
    h.Unite(a,b)
ans=[h.Count(i)-len(f[i])-1 for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    if h.isSameGroup(a,b):
        ans[a]-=1
        ans[b]-=1
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

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 main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	uf = UnionFind(N)
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		uf.union(A,B)
		frend[A].append(B)
		frend[B].append(A)

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if uf.same(C,D):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = uf.size(i)-len(frend[i])-len(block[i])-1
		ans_v.append(ans)
	printH(ans_v)

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()
 
class UnionFind:
    def __init__(self, n):
        self.n = n + 1
        self.parents = [-1] * (n + 1)
        self.mem = [[] for _ in range(n+1)]
 
    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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        if not self.mem[root]:
            self.mem[root] = [i for i in range(1, self.n) if self.find(i) == root]
        return self.mem[root]
 
def main():
    N, M, K = map(int, input().split())
 
    friends = defaultdict(lambda : 1)
    friendsGroup = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friendsGroup.union(a, b)
        friends[a] += 1
        friends[b] += 1
 
    block_and_same = defaultdict(int)
    for _ in range(K):
        c, d = map(int, input().split())
        if friendsGroup.same(c, d):
            block_and_same[c] += 1
            block_and_same[d] += 1
 
    ans = [0] * (N + 1)
    for i in range(1, N+1):
        ans[i] = friendsGroup.size(i) - friends[i] - block_and_same[i]
    print(*ans[1:])
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


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


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

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

not_see = defaultdict(set)

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

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 main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	uf = UnionFind(N)
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		uf.union(A,B)
		frend[A].append(B)
		frend[B].append(A)

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if uf.same(C,D):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = uf.size(i)-len(frend[i])-len(block[i])
		ans_v.append(ans-1)
	printH(ans_v)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()

class UnionFind():
    """ Union-Find木の実装（ランクあり） """
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    # parent 親 マイナスだったら根で、絶対値が集合の数
        self.rank   = [0]*(n+1)     # rank 深さ

    def root(self, x):
        """ 木の根を求める """
        if self.parent[x] < 0:      # xが根
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  # 経路圧縮
            return self.parent[x]
            
    def unite(self, x, y):
        """ xとyの属する集合を併合 """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.root(x) == self.root(y) or x==y
    
    def size(self, x):
        """ xと同じ集合に属する数 """
        return -self.parent[self.root(x)]

N, M, K = map(int, input().split())
# friend = [[0]*N for _ in range(N)]
friend = defaultdict(lambda : 1)
uf = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    friend[A] += 1
    friend[B] += 1
    uf.unite(A, B)

# block = [[0]*N for _ in range(N)]
block = defaultdict(int)
for j in range(K):
    C, D = map(int, input().split())
    if uf.isSame(C, D):
        block[C] += 1
        block[D] += 1

ans = [0] * (N+1)
for i in range(1, N+1):
    ans[i] = uf.size(i) - friend[i] - block[i]
print(*ans[1:])

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())
friend = UnionFind(n)
dataf = defaultdict(lambda: 0)

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

for _ in range(k):
    a, b = map(int, input().split())
    if friend.same(a-1, b-1):
        dataf[a-1] += 1
        dataf[b-1] += 1

for i in range(n):
    kouho = friend.size(i)
    print(kouho-dataf[i]-1, end=' ')

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#import math

#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
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())
AB=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    AB[i][0]-=1
    AB[i][1]-=1
CD=[list(map(int,input().split())) for i in range(K)]
for i in range(K):
    CD[i][0]-=1
    CD[i][1]-=1


uf=UnionFind(N)
fblst=[set() for i in range(N)]
blocklst=[0 for i in range(N)]
for a,b in AB:
    uf.union(a,b)
    fblst[a].add(b)
    fblst[b].add(a)


for c,d in CD:
    if uf.same(c,d):
        blocklst[c]+=1
        blocklst[d]+=1

lst=[]
for i in range(N):
    lst.append(uf.size(i)-len(fblst[i])-blocklst[i]-1)


print(" ".join(list(map(str,lst))))

Submission status: Accepted

Solution code:
import bisect


class UnionFind():
    
    def __init__(self, n):
        self.n = next
        self.parent = [-1 for i in range(n)]
    
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        else:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parent[self.find(x)]
    
    def __str__(self):
        return str(self.parent)



def read():
    N, M, K = list(map(int, input().strip().split()))
    uf = UnionFind(N)
    friends = [list() for i in range(N+1)]
    blocked = [list() for i in range(N+1)]
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        friends[a].append(b)
        friends[b].append(a)
        uf.unite(a-1, b-1)
    for i in range(K):
        c, d = list(map(int, input().strip().split()))
        blocked[c].append(d)
        blocked[d].append(c)
    return N, M, K, friends, blocked, uf


def solve(N, M, K, friends, blocked, uf):
    n_friendships = [0 for i in range(N)]
    for i in range(1, N+1):
        n = uf.size(i-1)
        m = len(friends[i])
        k = 0
        for b in blocked[i]:
            if uf.same(i-1, b-1):
                k += 1
        n_friendships[i-1] = n-1-m-k
    return ' '.join(map(str, n_friendships))


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))