Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

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

N, M, K = map(int, input().split())
F = []
for i in range(M):
	F.append(list(map(int, input().split())))
B = []
for i in range(K):
	B.append(list(map(int, input().split())))

def get_group(F):
	def root(a):
		p = G[a]
		while p != G[p]:
			p = G[p]
		while a != p:
			a, G[a] = G[a], p
		return p
	def union(a, b):
		ra = root(a)
		rb = root(b)
		if ra == rb: return
		G[ra] = rb
	G = [i for i in range(N)]
	for a, b in F:
		a -= 1
		b -= 1
		union(a, b)
	for i in range(N):
		G[i] = root(i)
	return G

def calc_count(F, G):
	edges = collections.defaultdict(set)
	for a, b in F:
		a -= 1
		b -= 1
		if G[a] == G[b]:
			edges[a].add(b)
			edges[b].add(a)
	cnt = [0] * N
	for i in range(N):
		cnt[i] = len(edges[i])
	return cnt

def get_num(c, f, b):
	ret = (c-1) - f - b
	return ret

G = get_group(F)
C = collections.Counter(G)
FC = calc_count(F, G)
BC = calc_count(B, G)
ans = [0] * N
for i in range(N):
	ans[i] = get_num(C[G[i]], FC[i], BC[i])

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

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
blsiz=[0 for i in range(n)]
ans=[0]*n
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    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
        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
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
uf=UnionFind(n)
for i in range(n):
  for j in relfr[i]:
    uf.Unite(i,j)
for i in range(n):
  for j in relbl[i]:
    if uf.isSameGroup(i,j):
      blsiz[i]+=1
for i in range(n):
  ans[i]=uf.Count(i)-len(relfr[i])-blsiz[i]-1

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

Submission status: Accepted

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

    def find(self, x):#要素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が属するグループと要素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):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):#要素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):#all_group_members O(N)かかるので注意
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 

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

uf=UnionFind(n+1)
ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

for i in range(k):
    cd.append(list(map(int,input().split())))



for i in range(m):
   # print("gn")
    a=ab[i][0]
    b=ab[i][1]
    if uf.same(a,b)==False:
        uf.union(a,b)
friend=[]
for i in range(1,n+1):#グループ分けをする（友達でも友達候補でもブロック関係でもカウント
    friend.append(uf.size(i))

block=[1]*n
for i in range(m):#友達のところは友達候補にならない
    a=ab[i][0]-1
    b=ab[i][1]-1
    block[a]+=1
    block[b]+=1
"""
for i in range(n):
    print(block[i],end=" ")
print()
"""
for i in range(k):
    a=cd[i][0]
    b=cd[i][1]
    if uf.same(a,b)==True:#そもそも友達候補関係になってなかったら
        block[a-1]+=1
        block[b-1]+=1

"""
for i in range(n):
    print(friend[i],end=" ")
print()"""
"""
for i in range(n):
    print(block[i],end=" ")
print()
"""
for i in range(n):
    print(friend[i]-block[i],end=" ")
#print()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
friends = [set() for _ in range(n+1)]
blocked = [set() for _ in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for i in range(k):
    c,d = map(int, input().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
    stack = list(friends[i])
    chain = set()
    while stack:
        f = stack.pop()
        if f in checked:
            continue
        chain.add(f)
        checked.add(f)
        stack.extend(friends[f])
    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):
        super().__init__()
        self.rank = [0] * n
        self.parent = [i for i in range(n)]
        self.counter = [1] * n

    def print_set(self):
        print(self.parent)
        print(self.rank)

    def find_set(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        
        return self.parent[x]
    
    def unite(self, x, y):
        if self.same(x, y):
            return

        x_parent = self.find_set(x)
        y_parent = self.find_set(y)

        if self.rank[x_parent] > self.rank[y_parent]:
            self.parent[y_parent] = x_parent
            self.counter[x_parent] += self.counter[y_parent]
        else:
            self.parent[x_parent] = y_parent
            self.counter[y_parent] += self.counter[x_parent]
            if self.rank[x_parent] == self.rank[y_parent]:
                self.rank[y_parent] += 1


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


n, m, k = map(int, input().split())
friend = UnionFind(n)
friend_list = [list(map(int, input().split())) for _ in range(m)]
block_list = [list(map(int, input().split())) for _ in range(k)]

for a, b in friend_list:
    friend.unite(a-1, b-1)

ans = [friend.counter[friend.find_set(i)]-1 for i in range(n)]

for a, b in friend_list:
    if friend.same(a-1, b-1):
        ans[a-1] -= 1
        ans[b-1] -= 1

for c, d in block_list:
    if friend.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

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

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()
friend = [LIST() for i in range(M)]
block = [LIST() for i in range(K)]

tree = UnionFind(N)

straight_friend = defaultdict(list)
straight_block = defaultdict(list)

for a, b in friend:
    tree.union(a-1, b-1)
    straight_friend[a-1].append(b-1)
    straight_friend[b-1].append(a-1)

for c, d in block:
    straight_block[c-1].append(d-1)
    straight_block[d-1].append(c-1)

for i in range(N):
    # print(tree.members(i))
    # print(straight_block[i])
    # print(straight_friend[i])
    exclude = 0
    for b in straight_block[i]:
        if tree.same(i, b):
            exclude += 1
    ans = tree.size(i)- exclude - len(straight_friend[i]) - 1
    # print(ans)
    # ans = ans - len(straight_friend[i]) - 1
    print(ans, end=" ")

print()

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

n,m,k=map(int, input().split())
friend=[[] for i in range(n+1)]
block_count=[0]*(n+1)
uf=UnionFind(n+1)
for i in range(1,m+1):
    a,b=map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)
    uf.union(a,b)

for i in range(1,k+1):
    a,b=map(int, input().split())
    if uf.same(a,b)==True:
        block_count[a]+=1
        block_count[b] += 1

answer=[0]*(n)
for i in range(1,n+1):
    answer[i-1]=uf.size(i)-len(friend[i])-block_count[i]-1
    #print(uf.size(i))

print(" ".join(map(str,answer)))
#print(friend)
#print(uf)
#print(block_count)

Submission status: Accepted

Solution code:
class union():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
        self.counts = [1] * n
        self.block_counts = [0] * n
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
        if self.same(a, b):
            self.block_counts[a] += 1
            self.block_counts[b] += 1
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.counts[y] += self.counts[x]
        else:
            self.par[y] = x
            self.counts[x] += self.counts[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    unite = u.unite
    block = u.block
    for a, b in AB:
        unite(a, b)
    for c, d in CD:
        block(c, d)
    counts = u.counts
    par = u.par
    friends = u.friends
    block_counts = u.block_counts
    result = [str(counts[u.find(i)] - friends[i] - block_counts[i] - 1) for i in range(N)]
    print(" ".join(result))
main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+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
  
  #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 = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  for _ in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  for i in range(n):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, N):
        self.follow = [-1]*(N+1)
        self.num_follower = [1]*(N+1)

    def root_index_of(self, a):
        r = a
        while self.follow[r] > -1:
            r = self.follow[r]
        return r
    
    def connet(self, a, b):
        ra = self.root_index_of(a)
        rb = self.root_index_of(b)
    
        if ra == rb:
            return
        
        if self.num_follower[ra] < self.num_follower[rb]:
            self.follow[ra] = rb
            self.follow[a] = rb
            self.num_follower[rb] += self.num_follower[ra]
        else:
            self.follow[rb] = ra
            self.follow[b] = ra
            self.num_follower[ra] += self.num_follower[rb]
    
    def conneted(self, a, b):
        return self.root_index_of(a) == self.root_index_of(b)

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

cnt_friends = [0]*(N+1)
for i in range(M):
    A, B = map(int, input().split())
    U.connet(A, B)
    cnt_friends[A] += 1
    cnt_friends[B] += 1

cnt = [0]*(N+1)
for i in range(1, N+1):
    r = U.root_index_of(i)
    cnt[i] = U.num_follower[r] - (cnt_friends[i]+1)

for i in range(K):
    C, D = map(int, input().split())
    if U.conneted(C, D):
        cnt[C] -= 1
        cnt[D] -= 1
print(*cnt[1:])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+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
  
  #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 = map(int, input().split())
  deg = [0]*n
  ans = [0]*n
  uf = UnionFind(n)
  for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.union(a, b)
  
  for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  
  for i in range(n):
    ans[i] = uf.size(i) - 1 -deg[i]
  
  print(' '.join(map(str, ans)))
  
if __name__ == '__main__':
  main()

Submission status: Accepted

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

# Union Findデータ構造


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

group = UnionFind(n)

friends_num = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    group.union(a, b)
    friends_num[a] += 1
    friends_num[b] += 1

block_list = [[] for _ in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    block_list[c].append(d)
    block_list[d].append(c)

# print(friends_dict)
# print(block_dict)

for i in range(group.n):
    count = group.size(i) - 1 - friends_num[i]
    for j in block_list[i]:
        if j in block_list[i]:
            if group.same(i, j):
                count -= 1

    print(count, "", end="")

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


def main():
    N, M, K = map(int, input().split())
    num_friends = [0 for _ in range(N)]
    blocks = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(int, input().split())
        num_friends[a-1] += 1
        num_friends[b-1] += 1
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)

    ans = []
    for i in range(N):
        cnt = uf.size(i) - 1 - num_friends[i]
        for j in blocks[i]:
            if uf.same(i, j):
                cnt -= 1
        ans.append(cnt)
    
    print(*ans)

if __name__ == "__main__":
    main()

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


def main():
    N, M, K = map(int, input().split())
    num_friends = [0 for _ in range(N)]
    blocks = [set() for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(int, input().split())
        num_friends[a-1] += 1
        num_friends[b-1] += 1
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1].add(b-1)
        blocks[b-1].add(a-1)

    ans = []
    for i in range(N):
        cnt = uf.size(i) - 1 - num_friends[i]
        for j in blocks[i]:
            if uf.same(i, j):
                cnt -= 1
        ans.append(cnt)
    
    print(*ans)

if __name__ == "__main__":
    main()

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


def main():
    N, M, K = map(int, input().split())
    num_friends = [0 for _ in range(N)]
    blocks = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(int, input().split())
        num_friends[a-1] += 1
        num_friends[b-1] += 1
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)

    for i in range(N):
        cnt = uf.size(i) - 1 - num_friends[i]
        for j in blocks[i]:
            if uf.same(i, j):
                cnt -= 1
        print(cnt, end=' ')

if __name__ == "__main__":
    main()

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


def main():
    N, M, K = map(int, input().split())
    num_friends = [0 for _ in range(N)]
    blocks = [[] for _ in range(N)]
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        num_friends[a-1] += 1
        num_friends[b-1] += 1
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)

    for i in range(N):
        cnt = uf.size(i) - 1 - num_friends[i]
        for j in blocks[i]:
            if uf.same(i, j):
                cnt -= 1
        print(cnt, end=' ')
        

if __name__ == "__main__":
    main()