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

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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #xの属するグループの要素一覧
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self): #根の一覧
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self): #グループ個数
        return len(self.roots())

    def all_group_members(self): #根とその要素の辞書配列
        return {r: self.members(r) for r in self.roots()}

    def __str__(self): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if U.same(a,b):
        K[a].append(b)
        K[b].append(a)

ans=[]
for i in range(n):
    m=M[i]
    k=K[i]
    ans.append(U.size(i)-len(m)-len(k)-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)

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


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    uf = UnionFind(n)

    friendlist = dict()
    for i in range(m):
        tmp = list(map(int, input().split()))
        uf.union(tmp[0]-1, tmp[1]-1)
        if tmp[0] - 1 not in friendlist:
            friendlist[tmp[0]-1] = [tmp[1]-1]
        else:
            friendlist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in friendlist:
            friendlist[tmp[1]-1] = [tmp[0]-1]
        else:
            friendlist[tmp[1]-1].append(tmp[0]-1)

    blocklist = dict()
    for i in range(k):
        tmp = list(map(int, input().split()))
        if tmp[0] - 1 not in blocklist:
            blocklist[tmp[0]-1] = [tmp[1]-1]
        else:
            blocklist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in blocklist:
            blocklist[tmp[1]-1] = [tmp[0]-1]
        else:
            blocklist[tmp[1]-1].append(tmp[0]-1)

    ans = list()
    for i in range(n):
        blocknum = 0
        if i in blocklist:
            for ii in blocklist[i]:
                if uf.find(ii) == uf.find(i):
                    blocknum += 1
        friendnum = 0
        if i in friendlist:
            friendnum = len(friendlist[i])

        print(str(uf.size(i) - friendnum - blocknum - 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
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):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 親
        self.rank = [1]*n  # 木の高さ
        self.size = [1]*n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]
    
N, M, K = map(int, input().split())
A, B, C, D = [0]*M, [0]*M, [0]*K, [0]*K
for i in range(0, M):
    A[i], B[i] = map(int, input().split())
for i in range(0, K):
    C[i], D[i] = map(int, input().split())

friend, block = [0]*N, [0]*N
uf = UnionFind(N)
for i in range(0, M):
    friend[A[i]-1] = friend[A[i]-1]+1
    friend[B[i]-1] = friend[B[i]-1]+1
    uf.union(A[i]-1, B[i]-1)
for i in range(0, K):
    if uf.is_same(C[i]-1, D[i]-1):
        block[C[i]-1] = block[C[i]-1]+1
        block[D[i]-1] = block[D[i]-1]+1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

class UnionFind():  
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    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)

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

    # 要素x, yが同じグループに属するかどうかを返す
    def is_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, inp().split())
uf = UnionFind(N)
ans = [0]*N
not_friend = [1]*N # 自分自身

for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uf.union(a, b)
  not_friend[a] += 1
  not_friend[b] += 1
  
for _ in range(K):
  c, d = map(int, input().split())
  c -= 1
  d -= 1
  if uf.is_same(c, d):
    not_friend[c] += 1
    not_friend[d] += 1  
    
ans = [uf.size(i) - not_friend[i] for i in range(N)]    
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
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def unite(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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

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

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

ans = []
for i in range(N):
    ans.append(uf.size(i) - 1 - len(blocks[i]) - len(friends[i]))
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def unite(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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

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

roots = uf.roots()
for r in roots:
    size = uf.size(r)
    root[r] = size - 1

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

ans = []
for i in range(N):
    ans.append(root[uf.find(i)] - len(blocks[i]) - len(friends[i]))
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

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

a = []
b = []
c = []
d = []
for _ in range(m):
	tmp = list(map(int,input().split()))
	a.append(tmp[0]-1)
	b.append(tmp[1]-1)
for _ in range(k):
	tmp = list(map(int,input().split()))
	c.append(tmp[0]-1)
	d.append(tmp[1]-1)

class UnionFind():
    def __init__(self, n):
        self.n = n
        #self.parents = -1 : 親が自分で子も自分(独立)
        #self.parents = n(>0) : 親が自分でなく頂点n
        #self.parents = n(<0) : 親が自分で、子が-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]
    #xとyを同じ親に属させる
    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
    #同じ親だったらTrue
    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
    	return self.parents[self.find(x)] * -1

uf = UnionFind(n)
ans = []

for i in range(m):
	uf.union(a[i],b[i])

for i in range(n):
	ans.append(uf.size(i)-1) #-1してるのは、自分自身を除くため

for i in range(m):
	if uf.find(a[i]) == uf.find(b[i]):
		ans[a[i]] -= 1
		ans[b[i]] -= 1

for i in range(k):
	if uf.find(c[i]) == uf.find(d[i]):
		ans[c[i]] -= 1
		ans[d[i]] -= 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

N, M, K = map(int, inp().split())
friends = [set() for _ in range(N+1)]
blocked = [set() for _ in range(N+1)]

for _ in range(M):
  a, b = map(int, inp().split())
  friends[a].add(b)
  friends[b].add(a)
for _ in range(K):
  c, d = map(int, inp().split())
  blocked[c].add(d)
  blocked[d].add(c)  

checked = set()
ans = [0]*(N+1)
for i in range(1, N+1):
  if i in checked:
    continue
  chain = set()
  
  stack = list(friends[i])
  while stack:
    friend = stack.pop()
    if friend in checked:
      continue
      
    checked.add(friend)
    chain.add(friend)
    stack.extend(friends[friend])
  cnt = len(chain) - 1 # 自分を引く
  for c in chain:
    ans[c] += cnt - len(chain & (friends[c] | blocked[c]))
    
print(*ans[1:])

Submission status: Accepted

Solution code:
class Unionfind():

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

    def find(self,a):
        if self.parents[a]<0:
            return a
        else:
            self.parents[a]=self.find(self.parents[a])##事実上for文
            return self.parents[a]


    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        else:
            if self.parents[x]<self.parents[y]:
                x,y=y,x
            self.parents[y]+=self.parents[x]
            self.parents[x]=y

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

    def same(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False
          
N,M,K=map(int,input().split())
uf=Unionfind(N)
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
ff=[[] for i in range(N)]
bb=[[] for i in range(N)]
ans=[]
for i in range(M):
    uf.union(friend[i][0]-1,friend[i][1]-1)
    ff[friend[i][0]-1].append(friend[i][1]-1)
    ff[friend[i][1]-1].append(friend[i][0]-1)
for i in range(K):
    bb[block[i][0]-1].append(block[i][1]-1)
    bb[block[i][1]-1].append(block[i][0]-1)
for i in range(N):
    ans.append(uf.size(i)-1-(len(ff[i])))
    for j in bb[i]:
        if uf.same(j,i)==True:
            ans[i]-=1
answer=[str(ans[i]) for i in range(len(ans))]
print(" ".join(answer))

Submission status: Accepted

Solution code:
class UnionFind:

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

    def find(self, n):
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]

    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.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] = self.rank[y] + 1

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

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

UF = UnionFind(N)
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)

for i in range(N):
    for f in F[i]:
        UF.union(i, f)

ans = [UF.size[UF.find(i)]-1 for i in range(N)]

for i in range(N):
    ans[i] -= len(F[i])

for i in range(N):
    for b in B[i]:
        if UF.same(i, b):
            ans[i] -= 1

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
#d

        
#     import sys
#     input = sys.stdin.readline

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

friends_pair=[]
friend=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    friends_pair.append((a,b))
    friend[a].append(b)
    friend[b].append(a) 
        
    
block=[]
for i in range(k):
    a,b = map(int,input().split())
    block.append((a-1,b-1))

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0

for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
#             if y == parent:#親ノードを飛ばし
#                 continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)

Submission status: Accepted

Solution code:
#d

        
#     import sys
#     input = sys.stdin.readline

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

friends_pair=[]
friend=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    friends_pair.append((a,b))
    friend[a].append(b)
    friend[b].append(a) 
        
    
block=[]
for i in range(k):
    a,b = map(int,input().split())
    block.append((a-1,b-1))

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
# while sum(visited)<n:
#     for i in range(n):
#         if visited[i]==0:
#             start=i
#             break
for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
dame = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    dame[A].add(B)
    dame[B].add(A)
for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        dame[C].add(D)
        dame[D].add(C)


ans = []
for n in range(N):
    ans.append(uf.size(n) - len(dame[n]) - 1)

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

Submission status: Accepted

Solution code:
maxn = 100000

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

par = [0] * (n+1)
rank = [0] * (n+1)

#初期化
for i in range(n+1):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

a = [0]*m
b = [0]*m
        
for i in range(m):
    a[i] ,b[i]  = map(int, input().split())
    unite(a[i] ,b[i] )
    
from collections import Counter
par2 = [find(i) for i in range(n+1)]
s = Counter(par2)
ans = [s[i] for i in par2]

for i in range(m):
    ans[a[i]] -= 1
    ans[b[i]] -= 1

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

ans = [ans[j]-1 for j in range(1,n+1)]
print(*ans)

Submission status: Accepted

Solution code:
class UnionFindTrees:
    def __init__(self, n):
        self.parent = [-1] * n

    def find_root(self, x):
        p = self.parent
        while (0 <= p[x]):
            x, p[x] = p[x], p[p[x]]
        return x

    def unite(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        p = self.parent
        if (x_root == y_root):
            return
        if p[x_root] > p[y_root]:
            x_root, y_root = y_root, x_root
        # root の parent は -size になるようにする
        p[x_root], p[y_root] = (p[x_root] + p[y_root]), x_root

    def size(self, x):
        return -self.parent[self.find_root(x)]

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


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
friend_trees = UnionFindTrees(n)
friend_or_block_cnts = [0] * n

for a, b in ab:
    friend_trees.unite(a, b)
    friend_or_block_cnts[a] += 1
    friend_or_block_cnts[b] += 1
for c, d in cd:
    if friend_trees.is_same_set(c, d):
        friend_or_block_cnts[c] += 1
        friend_or_block_cnts[d] += 1

print(*[(friend_trees.size(i) - friend_or_block_cnts[i] - 1) for i in range(n)])

Submission status: Accepted

Solution code:
from sys import exit
from collections import Counter
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

if M == 0:
    print(*np.zeros(N, dtype="int8"))
    exit()

exc = [set() for _ in range(N)]
edge = []

for _ in range(M):
    a, b = map(int, input().split())
    exc[a - 1].add(b - 1)
    exc[b - 1].add(a - 1)
    edge.append((a - 1, b - 1))

edge = np.array(edge).T
matr = csr_matrix((np.ones(M, dtype="int64"), edge), (N, N))
_, labels = connected_components(matr)
ct = Counter(labels)

for _ in range(K):
    c, d = map(int, input().split())
    if labels[c - 1] == labels[d - 1]:
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [ct[labels[i]] - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
al = [0 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, a, b,l):
        x = self.find(a)
        y = self.find(b)
        l[a] -= 1
        l[b] -= 1

        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())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1,al)
#print(al)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        al[c-1] -= 1
        al[d-1] -= 1
for i in range(n):
    print(uf.size(i)+al[i]-1,end=" ")

Submission status: Accepted

Solution code:
from sys import exit
from collections import Counter
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

if M == 0:
    print(*[0 for _ in range(N)])
    exit()

for _ in range(M):
    a, b = map(int, input().split())
    exc[a - 1].add(b - 1)
    exc[b - 1].add(a - 1)
    edge.append((a - 1, b - 1))

edge = np.array(edge).T
matr = csr_matrix(([1 for _ in range(M)], edge), (N, N))
_, labels = connected_components(matr)
ct = Counter(labels)

for _ in range(K):
    c, d = map(int, input().split())
    if labels[c - 1] == labels[d - 1]:
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [ct[labels[i]] - len(exc[i]) - 1 for i in range(N)]
print(*ans)