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:
# -*- coding:utf-8 -*-
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans


def solve():
    N, M, K = list(map(int, input().split()))
    uf = UnionFindVerSize(N)
    candidates = [-1 for _ in range(N)]

    for _ in range(M):
        a, b = list(map(int, input().split()))
        a, b = a-1, b-1
        uf.unite(a, b)
        candidates[a] -= 1
        candidates[b] -= 1

    for _ in range(K):
        c, d = list(map(int, input().split()))
        c, d = c-1, d-1
        if uf.is_same_group(c, d):
            candidates[c] -= 1
            candidates[d] -= 1

    for i in range(N):
        candidates[i] += uf.get_size(i)

    print(*candidates)




if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n
		self.exclued = [0] * 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.exclued[x] += self.exclued[y] + 1
		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()}

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

cnt = [0 for _ in range(n)]
uf = UnionFind(n)

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

for _ in range(k):
	c, d = list(map(int, input().split()))
	if uf.same(c - 1, d - 1):
		cnt[c - 1] += 1
		cnt[d - 1] += 1

ans = []
for i in range(n):
	ans.append(uf.size(i) - cnt[i] - 1)

print(" ".join([str(x) for x in ans]))

Submission status: Accepted

Solution code:

class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n)
        self.rnk = [0]*(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.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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

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

    def get_root(self):
        return self.root

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


N, M, K = map(int, input().split())
union_find = UnionFind(N)
AB = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a, b = a-1,b-1
    AB[a].append(b)
    AB[b].append(a)
    union_find.unite(a, b)

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

for i in range(N):
    union_find.find_root(i)

ret = [0] * N
for i in range(N):
    ret[i] += union_find.get_member(i)

for i in range(N):
    for a in AB[i]:
        if union_find.is_same_group(i, a):
            ret[i] -= 1
    for c in CD[i]:
        if union_find.is_same_group(i, c):
            ret[i] -= 1

print(" ".join([str(i-1) for i in ret]))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1] * n
        # cntはグループ数
        self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        self.cnt -= 1
        self.size_table[ru] += self.size_table[rv]
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def main():
    n, m, k = MI()
    uf = UnionFind(n)
    ans = [-1] * n
    for _ in range(m):
        a, b = MI1()
        uf.merge(a, b)
        ans[a]-=1
        ans[b] -= 1
    for i in range(n):ans[i]+=uf.size(i)
    for _ in range(k):
        a, b = MI1()
        if uf.root(a)==uf.root(b):
            ans[a]-=1
            ans[b]-=1
    print(*ans)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**5)

def main():
    N, M, K = map(int, input().split())
    parent = [n for n in range(0, N+1)]
    depth  = [1 for _ in range(0, N+1)] 
    blocks = [[] for _ in range(0, N+1)]
    friends = [[] for _ in range(0, N+1)]

    def root(x):
        p = parent[x]
        if p == x:
            return x
        p = root(p)
        parent[x] = p
        return p

    def union(a, b):
        pa = root(a)
        pb = root(b)
        if pa == pb:
            return
        if depth[pa] > depth[pb]:
            parent[pb] = pa
            depth[pa] += depth[pb]
        elif depth[pa] < depth[pb]:
            parent[pa] = pb
            depth[pb] += depth[pa]
        else:
            parent[pa] = pb
            depth[pb] *= 2
        #print((a, b), pa, pb, root(a), depth[2])

    for i in range(M):
        A, B = map(int, input().split())
        friends[A].append(B)
        friends[B].append(A)
        union(A, B)

    for i in range(K):
        C, D = map(int, input().split())
        blocks[C].append(D)
        blocks[D].append(C)
    if 0==1:
        print("index :", *range(1,N+1))
        print("parent:", *parent[1:])
        print("depth :", *[depth[root(x)] for x in range(1,N+1)])
        for n in range(1, N+1):
            p = root(n)
            c = depth[p]-1
            print(c, end=" ")
        print()

    for n in range(1, N+1):
        p = root(n)
        c = depth[p]-1
        for f in friends[n]:
            if root(f) == p:
                c-=1
        for b in blocks[n]:
            if root(b) == p:
                c-=1
        print(c, end=" ")
    print()

main()

Submission status: Accepted

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

class UnionFind(object):
    def __init__(self, N):
        # 初期状態を定義。ルートは -1から始まり、-X と負数でグループのサイズをもつ
        self.node = [-1] * N

    def root(self, x):
        if self.node[x] < 0:
            # それ自身がrootなら自分のポジションを返却
            return x
        else:
            # ルートを再帰で辿って、それぞれルートに直つなぎにする
            self.node[x] = self.root(self.node[x])
            # 自分がつながってるルートのポジションを返却
            return self.node[x]

    def size(self, x):
        # xが所属するグループのサイズを取得
        # サイズは負の数で管理されてるので、-1倍して返却
        return -self.node[self.root(x)]

    def connect(self, x, y):
        a = self.root(x)  # x のrootの位置
        b = self.root(y)  # y のrootの位置

        # もう同じグループなら何もしない
        if a == b:
            return

        # サイズが大きい方をaとして取り回す
        if self.size(a) < self.size(b):
            a, b = b, a

        # aのサイズをbのサイズを含む形に更新する（負数同士の足し算）
        self.node[a] += self.node[b]
        # bをaに連結する
        self.node[b] = a

        return

    def show_nodes(self):
        return self.node


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

    tree = UnionFind(N)

    friends = [ list(map(int, input().split())) for _ in range(M)]

    for A, B in friends:
        tree.connect(A-1, B-1)

    ans = [tree.size(x) - 1 for x in range(N)]

    for A, B in friends:
        if tree.root(A-1) == tree.root(B-1):
            ans[A-1] -= 1
            ans[B-1] -= 1

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

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda:inp.readline().decode('ascii')
buf = BytesIO()
sys.stdout.write = lambda s: buf.write(s.encode('ascii'))
atexit.register(lambda:sys.__stdout__.buffer.write(buf.getvalue()))

from collections import defaultdict as dd, deque

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

C = [[] for _ in range(n)]
B = [[] for _ in range(n)]

for _ in range(m):
    a,b = [int(x)-1 for x in input().split()]
    C[a].append(b)
    C[b].append(a)

for _ in range(k):
    a,b = [int(x)-1 for x in input().split()]
    B[a].append(b)
    B[b].append(a)

incluster = [-1]*n
for i in range(n):
    S = [i]
    while S:
        cur = S.pop()
        if incluster[cur] != -1:
            continue
        incluster[cur] = i
        for neigh in C[cur]:
            S.append(neigh)

clusters = dd(set)
for i in range(n):
    clusters[incluster[i]].add(i)

res =[]
for i in range(n):
    which = incluster[i]
    cluster = clusters[which]
    res.append(len(cluster) - sum(1 for b in B[i] if b in cluster) - len(C[i]) - 1)
print(*res)

Submission status: Accepted

Solution code:
n, m, k = [int(x) for x in input().split()]
fr = [i for i in range(n)]
dfr = [[] for i in range(n)]
bl = [[] for i in range(n)]
def deref(a):
    s = []
    while True:
        next = fr[a]
        if next == a:
            break
        s.append(a)
        a = next
    for i in s:
        fr[i] = a
    return a
def merge(a, b):
    ra, rb = deref(a), deref(b)
    fr[rb] = ra
for i in range(m):
    a, b = [int(x) - 1 for x in input().split()]
    dfr[a].append(b)
    dfr[b].append(a)
    a, b = min(a, b), max(a, b)
    merge(a, b)
for i in range(n):
    deref(i)
ss = [[] for i in range(n)]
for i in range(n):
    ss[fr[i]].append(i)
for i in range(k):
    c, d = [int(x) - 1 for x in input().split()]
    bl[c].append(d)
    bl[d].append(c)
for i in range(n):
    bl[i].sort()
r = []
for i in range(n):
    v = len(ss[fr[i]]) - len(dfr[i]) - 1
    v -= sum(fr[j] == fr[i] for j in bl[i])
    r.append(v)
print(' '.join(str(x) for x in r))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

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

P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if PP[j]==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n, m, k = map(int, input().split())
friendUnion = UnionFind(n)
friend = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    friendUnion.Unite(a - 1, b - 1)
    friend[a - 1].append(b - 1)
    friend[b - 1].append(a - 1)

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

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

ans = []
for i in range(n):
    tmp = friendUnion.Count(i) - 1 - len(friend[i]) 
    for j in block[i]:
        if friendUnion.isSameGroup(i, j):
            tmp -= 1
    ans.append(str(tmp))

print(' '.join(ans))

Submission status: Accepted

Solution code:
class UnionFindVerSize():
  def __init__(self, N):
    self._parent = [n for n in range(0, N)]
    self._size = [1] * N
  def find_root(self, x):
    if self._parent[x] == x: 
      return x
    self._parent[x] = self.find_root(self._parent[x]) 
    return self._parent[x]
  def unite(self, x, y):
    gx = self.find_root(x)
    gy = self.find_root(y)
    if gx == gy:
      return
    if self._size[gx] < self._size[gy]:
      self._parent[gx] = gy
      self._size[gy] += self._size[gx]
    else:
      self._parent[gy] = gx
      self._size[gx] += self._size[gy]
  def get_size(self, x):
    return self._size[self.find_root(x)]
  def is_same_group(self, x, y):
    return self.find_root(x) == self.find_root(y)
n,m,k = map(int,input().split())
f = [0 for _ in range(n+1)]
uf = UnionFindVerSize(n+1)
for i in range(m):
  ai,bi = map(int,input().split())
  uf.unite(ai,bi)
  f[ai] += 1
  f[bi] += 1
l = [[] for _ in range(n+1)]
for i in range(k):
  ci,di = map(int,input().split())
  l[ci].append(di)
  l[di].append(ci)
for i in range(1,n+1):
  bf = 0
  for x in l[i]:
    if uf.is_same_group(i,x):
      bf += 1
  print(uf.get_size(i)-bf-f[i]-1,end=" ")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class UnionFind():
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    
    N,M,K=map(int,input().split())
    ans=[-1]*N
    u=UnionFind(N)
    for _ in range(M):
        A,B=map(lambda x: int(x)-1,input().split())
        u.unite(A,B)
        ans[A]-=1
        ans[B]-=1
        
    for _ in range(K):
        C,D=map(lambda x: int(x)-1,input().split())
        if u.is_same(C,D):
            ans[C]-=1
            ans[D]-=1
    
    for i in range(N):
        ans[i]+=u.size(i)
    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
def main():

    N, M, K = map(int, input().split())
    friend = collections.defaultdict(set)
    for _ in range(M):
        A, B = map(int, input().split())
        friend[A].add(B)
        friend[B].add(A)
    block = collections.defaultdict(set)
    for _ in range(K):
        C, D = map(int, input().split())
        block[C].add(D)
        block[D].add(C)

    visited = set()
    ans = [0 for _ in range(N)]
    for i in range(1, N+1):
        if i not in visited:
            group = set([i])
            cur = set([i])
            while cur:
                temp = set()
                for j in cur:
                    for k in friend[j]:
                        if k not in group:
                            temp.add(k)
                            group.add(k)
                cur = temp

            for j in group:
                ans[j-1] = len(group) - len(friend[j]) - 1
                for k in block[j]:
                    if k in group: ans[j-1] -= 1
            visited |= group
    return " ".join(map(str, ans))

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,K = inputMap()
	UF = UnionFind(N)
	AB = {}
	for i in range(N):
		AB[i] = []
	for i in range(M):
		a,b = inputMap()
		a -= 1
		b -= 1
		UF.union(a, b)
		if a in AB:
			AB[a].append(b)

		if b in AB:
			AB[b].append(a)

	CD = {}
	for i in range(N):
		CD[i] = []
	for i in range(K):
		c,d = inputMap()
		c -= 1
		d -= 1
		if c in CD:
			CD[c].append(d)

		if d in CD:
			CD[d].append(c)

	ans = []
	for i in range(N):
		tmp = UF.getSize(i) - len(AB[i]) -1
		for j in CD[i]:
			if UF.is_same(i, j):
				tmp -= 1
		ans.append(tmp)

	print(*ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#https://www.kumilog.net/entry/union-find

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]

	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			# メンバ数の更新
			sum = self.size[x] + self.size[y]
			self.size[x] = sum
			self.size[y] = sum
			# 短いリストを長いリストのルートに繋ぎ直す
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x

	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	# x が属するグループのメンバ数を返却
	def getSize(self, x):
		par_x = self.find(x)
		return self.size[par_x]

# nCr mod m
# rがn/2に近いと非常に重くなる

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
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)]

import sys
sys.setrecursionlimit(1000000)

class uftree:
    def __init__(self, N):
        self.parent = list(range(N))
    def unite(self, a, b):
        ar = self.root(a)
        br = self.root(b)
        if ar != br: self.parent[max(ar, br)] = min(ar, br)
        return
    def root(self, a):
        p = self.parent[a]
        if a == p:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]


tree = uftree(N)
for i, (Ai, Bi) in enumerate(AB):
    tree.unite(Ai - 1, Bi - 1)
# print("#", tree.parent)

root = [tree.root(i) for i in range(N)]
# print("#", root)

cnt = {}
for i in range(N):
    cnt[str(root[i])] = cnt.setdefault(str(root[i]), 0) + 1
# print("#", cnt)

ans = [cnt[str(root[i])] - 1 for i in range(N)]

for i, (Ai, Bi) in enumerate(AB):
    if tree.root(Ai - 1) == tree.root(Bi - 1):
        ans[Ai - 1] -= 1
        ans[Bi - 1] -= 1
for i, (Ci, Di) in enumerate(CD):
    if tree.root(Ci - 1) == tree.root(Di - 1):
        ans[Ci - 1] -= 1
        ans[Di - 1] -= 1

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

Submission status: Accepted

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

def connected_components(graph):
  seen = set()
  def component(n):
    nodes = set([n])
    while nodes:
      n = nodes.pop()
      seen.add(n)
      nodes |= graph[n] - seen
      yield n
  for n in graph:
    if n not in seen:
      yield component(n)

n,m,k=map(int,input().split())
friend={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  friend[a-1].add(b-1)
  friend[b-1].add(a-1)
block={i:set() for i in range(n)}
for i in range(k):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)
c = connected_components(friend)
fnum=[-1 for i in range(n)]
for graph in c:
  s = set(graph)
  for x in s:
    fnum[x] = len(s) - len(s & block[x]) -len(friend[x])- 1
print(' '.join(map(str,fnum)))

Submission status: Accepted

Solution code:
def dfs(node,visited,friends,connected_compnts):
    cmpnt = set()
    stack = [node]
    while stack:
        curr = stack.pop()
        if curr not in visited:
            visited.add(curr)
            cmpnt.add(curr)
            for kid in friends[curr]:
                stack.append(kid)

    connected_compnts.append(cmpnt)

def solve(cmpnt,friends,blocks,ans):
    arr = list(cmpnt)
    for node in arr:
        cmpnt.remove(node)
        add = []
        for kid in friends[node]:
            if kid in cmpnt:
                add.append(kid)
                cmpnt.remove(kid)

        blocked = set()
        for block in blocks[node]:
            blocked.add(block)
            
        ans[node] = len(cmpnt)-len(cmpnt&blocked)
        cmpnt.add(node)
        for kid in add:
            cmpnt.add(kid)

def main():
    n,m,k = map(int,input().split())
    friends = {}
    blocks = {}

    for i in range(1,n+1):
        friends[i] = []

    for i in range(1,n+1):
        blocks[i] = []

    for i in range(m):
        a,b = map(int,input().split())
        friends[a].append(b)
        friends[b].append(a)

    for i in range(k):
        a,b = map(int,input().split())
        blocks[a].append(b)
        blocks[b].append(a)

    connected_compnts = []

    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            dfs(i,visited,friends,connected_compnts)

    ans = [0]*(n+1)
    for cmpnt in connected_compnts:
        solve(cmpnt,friends,blocks,ans)

    for i in range(1,n+1):
        print(ans[i],end = ' ')

main()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = []
cnt = [0 for _ in range(n)]
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(I)
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))