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:
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())
    uf=UnionFind(n)
    block={}
    for i in range(n):
        block[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        uf.union(a-1,b-1)
        block[a-1].append(b-1)
        block[b-1].append(a-1)
        
    for i in range(k):
        a,b=map(int,input().split())
        block[a-1].append(b-1)
        block[b-1].append(a-1)
    ans=[]
    #print(block)
    for i in range(n):
        res=uf.size(i)
    #   print(res)
        for value in block[i]:
            if uf.same(value,i):
                res-=1
        ans.append(res)
    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())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
friends = [0 for _ in range(N)]
blocks = [0 for _ in range(N)]

class Union():
    def __init__(self, N):
        self.Parent = []
        for i in range(N):
            self.Parent.append(-1)

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

    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        if(self.size(A) < self.size(B)):
            A, B = B, A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

uni = Union(N)
ans = []
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A] += 1
    friends[B] += 1
    uni.connect(A,B)

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if (uni.root(C) == uni.root(D)):
        blocks[C] += 1
        blocks[D] += 1

for i in range(N):
    ansi = max(0, uni.size(i) - friends[i] - blocks[i] - 1)
    ans.append(str(ansi))

print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),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]
        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 main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFind(n)
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a-1,b-1)
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
    blockc=[0]*n
    for c,d in CD:
        if un.same(c-1,d-1):
            blockc[c-1]+=1
            blockc[d-1]+=1
    for i in range(n):
        print(un.size(i)-1-blockc[i]-len(friend[i]))
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),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]
        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):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

def main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFind(n)
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a-1,b-1)
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
    blockc=[0]*n
    for c,d in CD:
        if un.same(c-1,d-1):
            blockc[c-1]+=1
            blockc[d-1]+=1
    for i in range(n):
        print(un.size(i)-1-blockc[i]-len(friend[i]))
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

n,m,k = map(int,input().split())
tree = UnionFind(n)
len_group = [0] * (n+1)
num_friend = [0] * (n+1)
num_block_sametree = [0] * (n+1)
root_ls = [0] * (n+1)
# 友達だったらブロックじゃない

for i in range(m):
    a,b = map(int,input().split())
    tree.union(a,b)
    num_friend[a] += 1
    num_friend[b] += 1
for i in range(k):
    c,d = map(int,input().split())
    if tree.same_check(c,d):
        num_block_sametree[c] += 1
        num_block_sametree[d] += 1
# 根を格納するハッシュ
for node in range(1,n+1):
    root = tree.find(node)
    root_ls[node] = root
    len_group[root] += 1

ans_ls = [0] * (n+1)
for node in range(1,n+1):
    root = root_ls[node]
    ans_ls[node] = len_group[root] - 1 - num_friend[node] - num_block_sametree[node]
ans_ls = list(map(str, ans_ls))
print(' '.join(ans_ls[1:]))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        #初期化[-1]*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,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が同じグループかどうか(同じならTrue)
        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):
        #Find-Treeの頂点
        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())
    """
    #遷移を確認したいときはこちらに書き換えて実行する(for以降の経路圧縮が行われていない)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)))
    """

def main():
    n, m, k = list(map(int,sys.stdin.readline().split()))
    uf = UnionFind(n)
    num_of_friends = [-1] * n

    for _ in range(m):
        a, b = list(map(int,sys.stdin.readline().split()))
        a -= 1
        b -= 1
        uf.union(a,b)
        num_of_friends[a] -= 1
        num_of_friends[b] -= 1
        #print(num_of_friends)
    #print(uf)
    """
    for i2 in range(n):
        roots[find(i2)] += 1
        print(roots)"""
    for i3 in range(n):
        num_of_friends[i3] += uf.size(i3)
        #print(num_of_friends)

    for _ in range(k):
        c, d = list(map(int,sys.stdin.readline().split()))
        c -= 1
        d -= 1
        """
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1
        """
        if uf.same(c,d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1    
    #print(num_of_friends)
    print(' '.join([str(number) for number in num_of_friends]))

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):																		#要素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):													#{ルート要素：[そのグループに含まれる要素のリスト]…}の辞書
		return {r: self.members(r) for r in self.roots()}

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


n,m,k=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
CD=[list(map(int,input().split())) for _ in range(k)]

U=UnionFind(n)

for a,b in AB:
	U.union(a-1,b-1)
	
res=[0]*n
for i in range(n):
	res[i]=U.size(i)-1
for a,b in AB:
	res[a-1]-=1
	res[b-1]-=1
for c,d in CD:
	if U.same(c-1,d-1):
		res[c-1]-=1
		res[d-1]-=1

print(*res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1''などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,M,K = MI()
F = [[] for _ in range(N+1)]
B = [[] for _ in range(N+1)]
for i in range(M):
    a,b = MI()
    F[a].append(b)
    F[b].append(a)
for i in range(K):
    c,d = MI()
    B[c].append(d)
    B[d].append(c)
D = {}
visited = [False for _ in range(N+1)]
parent = [0 for _ in range(N+1)]

def dfs(i,root):
    if visited[i]:
        pass
    else:
        visited[i]=True
        parent[i] = root
        for next in F[i]:
            if visited[next]:
                continue
            D[root].add(next)
            dfs(next,root)


for root in range(1,N+1):
    if visited[root]:
        continue
    D[root]=set([root])
    dfs(root,root)
ans = [0]*N
for iam in range(1,N+1):
    temp_ans = len(D[parent[iam]])-len(F[iam])-1
    for block in B[iam]:
        if block in D[parent[iam]]:
            temp_ans -= 1
    ans[iam-1] = temp_ans

print(*ans)

Submission status: Accepted

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return

    # sizeの大きいほうがx
    if par[x] > par[y]:
        x, y = y, x
    
    par[x] += par[y]
    par[y] = x


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


def size(x):
    return -par[find(x)]


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

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

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

for i in range(n):
    ans = size(i) - friend[i] - 1
    for j in block[i]:
        if same(i, j):
            ans -= 1
    print(ans, end=' ')

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return

    # sizeの大きいほうがx
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x


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


def size(x):
    return -par[find(x)]


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

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

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

for i in range(n):
    ans = size(i) - friend[i] - 1
    for j in block[i]:
        if same(i, j):
            ans -= 1
    print(ans, end=' ')

Submission status: Accepted

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

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

def size(x):
    return -par[find(x)]

par = [-1] * n
friend = [0] * n

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

block = [[] for _ in range(n)]

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

for i in range(n):
    ans = size(i) - friend[i] - 1
    for j in block[i]:
        if same(i, j):
            ans -= 1
    print(ans, 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()) 
    uf = UnionFind(n)
    no_cnt_list = [ set() for _ in range(n)]
    for i in range(m):
        a, b = map(int, input().split()) 
        uf.union(a-1,b-1)
        no_cnt_list[a-1].add(b-1)
        no_cnt_list[b-1].add(a-1)

    for i in range(k):
        c, d = map(int, input().split()) 
        if uf.same(c-1,d-1):
            no_cnt_list[c-1].add(d-1)
            no_cnt_list[d-1].add(c-1)

    ans_l = []
    for i in range(n):
        all_cnt = uf.size(i)
        ans = all_cnt - 1 - len(no_cnt_list[i])
        ans_l.append(ans)

    print(*ans_l)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2 * 10 ** 9)

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

f_G = [[] for _ in range(N)]
for a, b in AB:
  a, b = a-1, b-1
  f_G[a].append(b)
  f_G[b].append(a)

b_G = [[] for _ in range(N)]
for c, d in CD:
  c, d = c-1, d-1
  b_G[c].append(d)
  b_G[d].append(c)

def dfs(v):
  if visited[v]:
    return
  visited[v] = True
  for nv in f_G[v]:
    s.add(nv)
    dfs(nv)  

ans = [0] * N
visited = [False] * N

for i in range(N):
  if not visited[i]:
    s = set()
    dfs(i)
    l = len(s)
    for u in s:
      ans[u] = l - 1
      ans[u] -= len(set(f_G[u]) & s)
      ans[u] -= len(set(b_G[u]) & s)

print(*ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
# list(map(int, input().split()))
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

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

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

N, M, K = getNM()

# グループ分けをして解いていく
U = UnionFind(N)

friendlist = [getList() for i in range(M)]
blockedlist = [getList() for i in range(K)]
# friendlist内のa, bを繋いでいく
for a, b in friendlist:
    U.union(a - 1, b - 1)

friends = [0] * (N + 1)
blocks = [0] * (N + 1)

# 「同じグループ内に」友達、ブロックが何人いるか
for a, b in friendlist:
    if U.same(a - 1, b - 1):
        friends[a - 1] += 1
        friends[b - 1] += 1
for a, b in blockedlist:
    if U.same(a - 1, b - 1):
        blocks[a - 1] += 1
        blocks[b - 1] += 1

ans = []
for i in range(N):
    # U.size: グループの大きさ
    cnt = U.size(i) - friends[i] - blocks[i] - 1
    ans.append(cnt)
print(*ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

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

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    
def dfs(v, temp):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(i, temp)
    return temp
visited = [False]*n

cc = [0]*n
for v in range(n):
    if visited[v] == False:
        c = dfs(v,set())
        for i in c:
            cc[i] = c


ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)