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**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds


def tree_init(N):
    edgelist = [[] for _ in range(N)]
    for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
        edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
        edgelist[b-1].append(a-1)
    return edgelist

def root(x,par):
    px=par[x]
    while px!=x:
        x=px
        px=par[x]
    return px
def union(x,y,par):
    rx,ry=root(x,par),root(y,par)
    if rx!=ry:
        par[ry]=rx 


def main():
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N,M,K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    par=[i for i in range(N)]
    fl=[[] for _ in range(N)]
    counts=[0]*N
    for _ in range(M):
        a, b= map(int,input().split())
        counts[a-1]-=1
        counts[b-1]-=1
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)

    visited=[False]*N
    roots=[0]*N
    pcount=[0]*N
    for i in range(N):
        if visited[i]:
            continue
        q=deque([i])
        while len(q):
            
            e=q.pop()
            if visited[e]:
                continue
            #print(e)
            roots[e]=i
            pcount[i]+=1
            visited[e]=True
            for ne in fl[e]:
                if visited[ne]:
                    continue
                q.append(ne)
    #print(pcount)

    for i in range(N):
        counts[i]+=pcount[roots[i]]-1

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

    print(*counts)
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()

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

	def find(self, x): # root
		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 -1*self.parents[self.find(x)]

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

	def members(self,x): # much time
		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()} # 1~n

n,m,k = readInts()

uf = UnionFind(n)
fc = [0]*(n+1) #friend count

for i in range(m):
	a,b = readInts()
	uf.union(a-1,b-1)
	fc[a]+=1
	fc[b]+=1

br = [0]*(n+1)

for i in range(k):
	c,d = readInts()
	if uf.find(c-1)==uf.find(d-1):
		br[c]+=1
		br[d]+=1

for i in range(1,n+1):
	print(uf.size(i-1)-1-fc[i]-br[i],end=" ")
print()

Submission status: Accepted

Solution code:
# D - Friend Suggestions

from queue import Queue

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

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

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

Q = Queue()
visited = [False] * N
group = [0] * N
for i in range(N):
    if visited[i]:
        continue
    Q.put(friends[i])
    visited[i] = True
    while not Q.empty():
        q = Q.get()
        group[q[0]] = i
        for j in q[1]:
            if not visited[j]:
                visited[j] = True
                Q.put(friends[j])

cnt = {}
for num in group:
    if num in cnt:
        cnt[num] += 1
    else:
        cnt[num] = 1

ans = [0] * N
for i in range(N):
    ans[i] = cnt[group[i]] - len(friends[i][1]) - 1
    for block in blocks[i][1]:
        if group[i] == group[block]:
            ans[i] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n,m,k = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for _ in range(m)]
cd = [[int(i) for i in readline().split()] for _ in range(k)]

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n # 負なら根、非負なら親IDの情報を持たせる。負の値の絶対値で連結成分のサイズを表す（-2なら連結成分サイズ2の根）

    def find(self, x):
        """
        根のIDを返す
        """
        if self.d[x] < 0: return x # 今の頂点が根なら頂点番号を返す
        self.d[x] = self.find(self.d[x]) # 今の頂点が根でないなら親についてfindクエリを投げる. d[x] = find(d[x])で経路縮約できる
        return self.d[x]

    def unite(self, x, y):
        """
        根同士をくっつける
        """
        x = self.find(x); y = self.find(y) # 根同士をくっつける
        if x == y: return False # 根が同じなら何もする必要はない。Falseを返しているのは、くっつけられたかどうかを返した方が便利なときがあるから（MSTなど）
        if self.d[x] > self.d[y]: x,y = y,x # 小さい方の部分木を大きい方の部分木にくっつけるためにswap。dがマイナスなので不等号が逆になる点に注意
        self.d[x] += self.d[y] # 連結成分サイズを更新
        self.d[y] = x # 根をyからxに張り替える
        return True

    def same(self, x, y):
        """
        同じ集合に所属しているかどうか
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        連結成分サイズを返す
        """
        return -self.d[self.find(x)]

MAXN = 100005
deg = [0]*MAXN
to = [[] for _ in range(MAXN)]

uf = UnionFind(n)

for a,b in ab:
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for c,d in cd:
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

anss = []
for i in range(n):
    ans = uf.size(i)-1-deg[i] # 連結成分サイズから自分自身と友達を引く
    for u in to[i]:
        if uf.same(i,u): ans -= 1 # 同じ連結成分にあってブロック関係にあったら友達候補にはなれないので-1する
    anss.append(ans)
print(*anss)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import Counter, defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, K = lr()

def find(A, x):
    parent = A[x]
    if parent == x: return x
    root = find(A, parent)
    A[x] = root
    return root

def union(A, x, y):
    root, second = find(A, x), find(A, y)
    if root > second:
        second, root = root, second
    A[second] = root

V = list(range(N+1))
friend = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    friend[a].append(b)
    friend[b].append(a)
    if find(V, a) != find(V, b):
        union(V, a, b)

V = [find(V, x) for x in V]
counter = Counter(V)
dic = defaultdict(int)
for k, v in counter.items():
    dic[k] = v

block = [[] for _ in range(N+1)]
for _ in range(K):
    c, d = lr()
    block[c].append(d)
    block[d].append(c)

answer = []
for i in range(1, N+1):
    root = V[i]
    x = dic[root] - 1
    x -= sum(1 for y in block[i] if V[y] == root)
    x -= sum(1 for y in friend[i] if V[y] == root)
    answer.append(x)

print(*answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N,M,K = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    groups = [[]]
    belongs = [-1] * (N+1)
    def dfs(node, g = 0 ,parent=None):
        seen[node] = True
        groups[g].append(node)
        belongs[node] = g
        for next in to[node]:
            if not seen[next]:
                dfs(next, g=g, parent=node)

    g = 0
    for idx in range(1, N+1):
        if not seen[idx]:
            dfs(idx, g)
            g += 1
            groups.append([])

    block = [[] for _ in range(N+1)]
    for _ in range(K):
        c,d = map(int, sysread().split())
        if belongs[c] == belongs[d]:
            block[c].append(d)
            block[d].append(c)

    for i in range(1, N+1):
        tmp_g = belongs[i]
        print(len(groups[tmp_g]) - len(to[i]) - len(block[i]) - 1, end=' ')



if __name__ == "__main__":
    run()

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)
import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]-=1
 lst[B-1]-=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]-=1
  lst[B-1]-=1
lst=[lst[i]+uf.size(i)-1 for i in range(N)]
L=[str(a) for a in lst]
L=' '.join(L)
print(L)

Submission status: Accepted

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

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

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

  if x == y:
   return

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

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

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

N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]-=1
 lst[B-1]-=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]-=1
  lst[B-1]-=1
lst=[lst[i]+uf.size(i)-1 for i in range(N)]
L=[str(a) for a in lst]
L=' '.join(L)
print(L)

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)

import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
ans=[0]*(N)
for i in [0]*M:
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]+=1
 lst[B-1]+=1
for i in [0]*K:
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]+=1
  lst[B-1]+=1
for i in range(N):
 ans[i]=uf.size(i)-lst[i]-1
L=[str(a) for a in ans]
L=' '.join(L)
print(L)

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

import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
ans=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]+=1
 lst[B-1]+=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]+=1
  lst[B-1]+=1
for i in range(N):
 ans[i]=uf.size(i)-lst[i]-1
L=[str(a) for a in ans]
L=' '.join(L)
print(L)

Submission status: Accepted

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

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

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

  if x == y:
   return

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

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

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

N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
ans=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]+=1
 lst[B-1]+=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]+=1
  lst[B-1]+=1
for i in range(N):
 ans[i]=uf.size(i)-lst[i]-1
L=[str(a) for a in ans]
L=' '.join(L)
print(L)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M, K = map(int, input().split())
friends = defaultdict(list)
blocked = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)

groups = {}
for i in range(N):
    if i in groups:
        continue
    group = {i}
    stack = [(i, None)]
    while stack:
        j, parent_id = stack.pop()
        group.add(j)
        groups[j] = group
        for k in friends[j]:
            if k != parent_id and k not in groups:
                stack.append((k, j))

ans = []
for i in range(N):
    g = groups[i]
    res = len(g) - len(friends[i]) - 1
    for b in blocked[i]:
        if groups[b] is g:
            res -= 1
    ans.append(res)
print(*ans)

Submission status: Accepted

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

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

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


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

UnionFind=UnionFind(n+1)
Friend=[0 for _ in range(n+1)]
for a,b in AB:
    Friend[a] +=1
    Friend[b] +=1
    UnionFind.Unite(a,b)
Block=[0 for _ in range(n+1)]
for c,d in CD:
    if UnionFind.isSameGroup(c,d):
        Block[c] +=1
        Block[d] +=1

A=[]
for i in range(1,n+1):
    A.append(UnionFind.size(i)-Friend[i]-Block[i]-1)
print(*A)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.ranks = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def find_root(self, node):
        parent_node = self.parents[node]
        if parent_node == node:
            return node
        else:
            root_node = self.find_root(parent_node)
            self.parents[node] = root_node  # reduction
            return root_node

    def is_same_group(self, one_node, other_node):
        one_root = self.find_root(one_node)
        other_root = self.find_root(other_node)
        return one_root == other_root

    def union(self, one_node, other_node):
        one_root = self.find_root(one_node)
        other_root = self.find_root(other_node)
        if one_root == other_root:
            return
        one_rank = self.ranks[one_root]
        other_rank = self.ranks[other_root]
        if one_rank < other_rank:
            self.parents[one_root] = other_root
            self.sizes[other_root] += self.sizes[one_root]
        else:
            self.parents[other_root] = one_root
            self.sizes[one_root] += self.sizes[other_root]
            if one_rank == other_rank:
                self.ranks[one_root] += 1

    def group_size(self, node):
        root_node = self.find_root(node)
        return self.sizes[root_node]


def main():
    N, M, K = list(map(int, input().split(' ')))
    non_suggested_users = [[] for _ in range(N)]
    friend_tree = UnionFind(N)
    for _ in range(M):
        a, b = list(map(int, input().split(' ')))
        one_user = a - 1
        other_user = b - 1
        friend_tree.union(one_user, other_user)
        non_suggested_users[one_user].append(other_user)
        non_suggested_users[other_user].append(one_user)
    for _ in range(K):
        c, d = list(map(int, input().split(' ')))
        one_user = c - 1
        other_user = d - 1
        if friend_tree.is_same_group(one_user, other_user):
            non_suggested_users[one_user].append(other_user)
            non_suggested_users[other_user].append(one_user)
    answer_list = list()
    for user in range(N):
        ans = friend_tree.group_size(user) - len(non_suggested_users[user]) - 1
        answer_list.append(str(ans))
    print(' '.join(answer_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)
 
#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
N,M,K = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N+1)
 
friends = [[]for i in range(0,N+1,1)]
block = [[]for i in range(0,N+1,1)]
for i in range(0,M,1):
    a,b = map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)
    unite(a,b)
for i in range(0,K,1):
    a,b=map(int,input().split())
    block[a].append(b)
    block[b].append(a)
 
countmem = [0]*N
for i in range(1,N+1,1):
    count = size(i)-1
    mem = []
    ma = mem.append
    for j in range(0,len(friends[i]),1):
        if same(i,friends[i][j]):
            count -=1
            ma(friends[i][j])
    for j in range(0,len(block[i]),1):
        if same(i,block[i][j]) and not(block[i][j] in mem):
            count -=1
    countmem[i-1]=count
 
print(*countmem)

Submission status: Accepted

Solution code:
#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,M,K = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N+1)

friends = [[]for i in range(0,N+1,1)]
block = [[]for i in range(0,N+1,1)]
for i in range(0,M,1):
    a,b = map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)
    unite(a,b)
for i in range(0,K,1):
    a,b=map(int,input().split())
    block[a].append(b)
    block[b].append(a)

for i in range(1,N+1,1):
    friends[i].extend(block[i])
    set(friends[i])

countmem = [0]*N
for i in range(1,N+1,1):
    count = size(i)-1
    for j in range(0,len(friends[i]),1):
        if same(i,friends[i][j]):
            count -=1
    countmem[i-1]=count

print(*countmem)

Submission status: Accepted

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

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

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

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

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

    def print_tree(self):
        print(self.rank)
        print(self.par)

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

uf = UnionFind(n)
ng = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    uf.union(a, b)

    ng[a].append(b)
    ng[b].append(a)

for i in range(k):
    c, d = map(int, input().split())
    c-=1
    d-=1
    if uf.is_same(c, d):
        ng[c].append(d)
        ng[d].append(c)

ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - len(ng[i]) - 1

print(*ans)

Submission status: Accepted

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

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)

UFT = UnionFind(N)
ans = [0 for _ in range(N)]

for _ in range(M):
    A, B = map(int,input().split())
    ans[A-1] -= 1
    ans[B-1] -= 1
    UFT.union(A-1, B-1)

for _ in range(K):
    C, D = map(int,input().split())
    if UFT.same(C-1, D-1):
        ans[C-1] -= 1
        ans[D-1] -= 1

ans = [UFT.size(i) + ans[i] - 1 for i in range(N)]

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n 
        self.size = [1] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] = self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
                
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    friends[x].append(y)
    friends[y].append(x)

for i in range(k):
    x, y = map(lambda x: int(x) - 1, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

uf = UnionFind(n)
for i in range(n):
    for f in friends[i]:
        uf.union(i, f)

# 自分を除くUnionFind木の大きさ
ans = [uf.size[uf.find(i)] - 1 for i in range(n)]
# 直接的な友達を引く
for i in range(n):
    ans[i] -= len(friends[i])

for i in range(n):
    for b in blocks[i]:
        if uf.same(i, b):
            ans[i] -= 1

print(*ans)

Submission status: Accepted

Solution code:


from collections import defaultdict
n, m, k = list(map(int, input().split()))
ns = defaultdict(set)
bs = defaultdict(set)
for i in range(m):
    a,b = list(map(int, input().split()))
    ns[a-1].add(b-1)
    ns[b-1].add(a-1)
for i in range(k):
    c,d = list(map(int, input().split()))
    bs[c-1].add(d-1)
    bs[d-1].add(c-1)
    
s = [0]
start = 0
parent = [None] * n
starts = defaultdict(int)
starts[0] = 0
notdone = set(list(range(n)))
notdone.remove(start)
while notdone or s:
    u = s.pop()
    parent[u] = start
    starts[start] += 1
    for v in ns[u]:
        if v in notdone:
            s.append(v)
            notdone.remove(v)
    if not s and notdone:
        start = notdone.pop()
        parent[start] = start
        s.append(start)
ans = [None] * n
for u in range(n):
    val = starts[parent[u]] - 1 - len(ns[u])
    for v in bs[u]:
        if parent[v]==parent[u]:
            val -= 1
    ans[u] = val
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):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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


N, M, K = map(int, input().split(" "))
uf = UnionFind(N)
deg = [1 for i in range(N)]
same = [0 for i in range(N)]

for _ in range(M):
    A, B = map(int, input().split(" "))
    uf.union(A - 1, B - 1)
    deg[A - 1] += 1
    deg[B - 1] += 1

for _ in range(K):
    C, D = map(int, input().split(" "))
    if uf.same(C - 1, D - 1):
        same[C - 1] += 1
        same[D - 1] += 1


ans = [uf.size(i) - deg[i] - same[i] for i in range(N)]
print(' '.join([str(a) for a in ans]))