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.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]
 

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

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

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

for i in range(n):
    ans=uf.group_size(i)-1-len(friend[i])-len(block[i])
    print(ans)

Submission status: Accepted

Solution code:
class Unionfind:
    def __init__(self, n):
        self.parents = [-1 for i in range(n)]
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def notsame(self, x, y):
        x = self.find(x)
        y = self.find(y)
        return False if x == y else True
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if x > y:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def belong_num(self, x):
        return -self.parents[self.find(x)]
    
N, M, K = map(int, input().split())
lists = [0 for i in range(N)]
uf = Unionfind(N)
for i in range(M + K):
    a, b = map(lambda x:int(x) - 1, input().split())
    if i < M:
        uf.union(a, b)     
    if uf.notsame(a, b) and i >= M:
        continue
    lists[a] += 1
    lists[b] += 1
    
for i in range(N):
    print(uf.belong_num(i) - lists[i] - 1, end=' ')
print()

Submission status: Accepted

Solution code:
from collections import deque


def dfs(start):
    link = {start}
    S = deque()
    # child = deque()
    visited[start] = 1
    S.append(start)
    while len(S) > 0:
        node = S.pop()
        # child.clear()
        for f in friend[node]:
            if visited[f] == 0:
                S.append(f)
                visited[f] = 1
                link.add(f)
    for i in link:
        res[i] = len(link) - len(link & friend[i]) - len(link & block[i]) - 1


N, M, K = map(int, input().split())
Friend = [list(map(int, input().split())) for _ in range(M)]
Block = [list(map(int, input().split())) for _ in range(K)]
visited = [0 for _ in range(N + 1)]
res = [0 for _ in range(N + 1)]

friend = [set() for _ in range(N + 1)]
block = [set() for _ in range(N + 1)]

for a, b in Friend:
    friend[a].add(b)
    friend[b].add(a)

for a, b in Block:
    block[a].add(b)
    block[b].add(a)

for i in range(1, N + 1):
    if visited[i] == 1:
        continue
    dfs(i)

print(*res[1:])

Submission status: Accepted

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[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)]


N, M, K = map(int, input().split())
NMAX = 100005
deg = [0] * NMAX
to = [[] for _ in range(NMAX)]
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
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
    anss.append(ans)
print(" ".join(map(str, anss)))

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_friend = UnionFind(N)

friend = [0] * N

for i in range(M):
    a, b = map(int,input().split())
    uf_friend.union(a-1,b-1)
    friend[a-1] += 1
    friend[b-1] += 1

block = [0] * N 
    
for i in range(K):
    c, d = map(int,input().split())
    if uf_friend.same(c-1,d-1):
        block[d-1] += 1
        block[c-1] += 1
    
ans = [0] * N

for i in range(N):
    ans[i] = uf_friend.size(i)-friend[i]-block[i]-1

print(*ans)

Submission status: Accepted

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
n, m, k = map(int, input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        
    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]
    
candidate = [-1] * (n + 1)
f_ship = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    candidate[a] -= 1
    candidate[b] -= 1
    f_ship.unite(a, b)
for _ in range(k):
    c, d = map(int, input().split())
    if f_ship.is_same(c, d):
        candidate[c] -= 1
        candidate[d] -= 1
for i in range(1, n + 1):
    candidate[i] += f_ship.size(i)
print(*candidate[1:])

Submission status: Accepted

Solution code:

def solve():
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                if len(us[i])>len(us[fr]):
                    us[i].extend(us[fr])
                    for aa in us[fr]:
                        us[aa] = us[i]
                else:
                    us[fr].extend(us[i])
                    for aa in us[i]:
                        us[aa] = us[fr]
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if us[i] is us[blo]:
                frens -= 1
        print(frens, end=" ")
    print()
    return



n, m, k = [int(s) for s in input().split(" ")]

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]
for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)


solve()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if x == y:
            return 
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

uf = UnionFind(N)
fr = [0]*(N+1)

for i in range(M):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    uf.Unite(x_tmp,y_tmp)
    fr[x_tmp] += 1
    fr[y_tmp] += 1

ans = [0]*(N+1)

for i in range(1,N+1):
    ans[i] = uf.Count(i) - fr[i] - 1
for j in range(K):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    if uf.isSameGroup(x_tmp,y_tmp):
        ans[x_tmp] -= 1
        ans[y_tmp] -= 1

print(' '.join(list(map(str,ans[1:]))))

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.group=[i for i in range(n)]
        self.size=[1 for i in range(n)]

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

    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            pass
        elif(self.sizeof(y) > self.sizeof(x)):
            self.group[x] = self.group[y]
            self.size[y] += self.size[x]
            self.size[x]=0
        else:
            self.group[y] = self.group[x]
            self.size[x] += self.size[y]
            self.size[y]=0

    def sizeof(self,a):
        return self.size[self.find(a)]

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

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


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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_root = self.find(a)
        b_root = self.find(b)
        if a_root == b_root:
            return
        else:
            if self.size_of(b_root) > self.size_of(a_root): 
                self.parent[a_root] = self.parent[b_root]
                self.size[b_root] += self.size[a_root]
            else:
                self.parent[b_root] = self.parent[a_root]
                self.size[a_root] += self.size[b_root]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.find(a) == self.find(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = [0]*(N+1)
for i in range(N+1):
    blocks.append([])
    friends.append(0)

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

for j in range(K):
    x,y = map(int, input().split())
    if uf.is_same(x,y):
        blocks[x] += 1
        blocks[y] += 1

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - blocks[i] -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_root = self.find(a)
        b_root = self.find(b)
        if a_root == b_root:
            return
        else:
            if self.size_of(b_root) > self.size_of(a_root): 
                self.parent[a_root] = self.parent[b_root]
                self.size[b_root] += self.size[a_root]
            else:
                self.parent[b_root] = self.parent[a_root]
                self.size[a_root] += self.size[b_root]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.find(a) == self.find(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = [0]*(N+1)
for i in range(N+1):
    blocks.append([])
    friends.append(0)

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

for j in range(K):
    x,y = map(int, input().split())
    if uf.is_same(x,y):
        blocks[x] += 1
        blocks[y] += 1

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - blocks[i] -1)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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
            if x != y:
                self.size[y] += self.size[x]
        else:
            self.par[y] = x
            if x != y:
                self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


u = UnionFind(n)
for a, b in ab:
    u.union(a, b)

removes = [0] * (n + 1)
for a, b in ab:
    if u.same_check(a, b):
        removes[a] += 1
        removes[b] += 1
for c, d in cd:
    if u.same_check(c, d):
        removes[c] += 1
        removes[d] += 1

ans = ''
for i in range(1, n + 1):
    tmp = u.get_size(i) - removes[i] - 1
    ans += str(tmp) + ' '
print(ans[:-1])

Submission status: Accepted

Solution code:
from sys import stdin


input = stdin.readline


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1] * n
    
  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)
    if a != b:
      if self.size[a] < self.size[b]:
        a, b = b, a
      self.size[a] += self.size[b]
      self.par[b] = a
      
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.size[self.find(a)]
    
  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]
  
   
N, M, K = map(int, input().split())
relation = UnionFind(N)

num_friends = [0] * N

for _ in range(M):
  a, b = map(lambda x: int(x) - 1, input().split())
  relation.unite(a, b)
  num_friends[a] += 1
  num_friends[b] += 1
  
# 所属するグループ - 友達 - 自分
num_candidates = [
  relation.size_of(i) - num_friends[i] - 1 
  for i in range(N)
]
  
for _ in range(K):
  a, b = map(lambda x: int(x) - 1, input().split())
  # ブロック関係かつ同じグループなら友達候補から除く
  if relation.is_same(a, b):
    num_candidates[a] -= 1
    num_candidates[b] -= 1
  
print(' '.join(str(num) for num in num_candidates))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

n,m,k = map(int,input().split())
Fri = [list(map(int, input().split())) for i in range(m)]
Bro = [list(map(int, input().split())) for i in range(k)]
dir = [0]*n
ans = [0]*n
temp = 0

ufF = UnionFind(n)

for i in range(m):
    ufF.union(Fri[i][0]-1, Fri[i][1]-1)
    dir[Fri[i][0]-1] += 1
    dir[Fri[i][1]-1] += 1

for i in range(k):
    if(ufF.same(Bro[i][0]-1, Bro[i][1]-1)):
        ans[Bro[i][0]-1] -= 1
        ans[Bro[i][1]-1] -= 1

for i in range(n):
    ans[i] += ufF.size(i) - 1 - dir[i]
    if(ans[i]<0):
        ans[i] = 0

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
par=[-1]*n

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 same(x,y):
  return find(x)==find(y)

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

F=[-1]*n
l = [] 
for _ in range(m):
  a,b=map(int,input().split())
  l.append([a-1,b-1])
  unite(a-1,b-1)
for _ in range(k):
  a,b=map(int,input().split())
  if same(a-1,b-1):
    F[a-1]-=1
    F[b-1]-=1
for i,j in l:
    if same(i,j):
        F[i]-=1
        F[j]-=1
for i in range(n):
  F[i]+=size(i)
# print(par)
print(*F)

Submission status: Accepted

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

fa = [x for x in range (n + 1)]
siz = [1 for i in range (n + 1)]
dep = [0 for i in range (n + 1)]
e = [1 for i in range (n + 1)]

def find (x) :
    if (fa[x] == x) :
        return x
    fa[x] = find (fa[x])
    return fa[x]

def uni (x, y) :
    u, v = find (x), find (y)
    if (dep[u] >= dep[v]) :
        fa[v] = u
        if (u != v) :
            siz[u] += siz[v]
        if (dep[u] == dep[v]) :
            dep[u] += 1
    else :
        fa[u] = v
        if (u != v) :
            siz[v] += siz[u]

for i in range (m) :
    a, b = list (map (int, input ().split ()))
    uni (a, b)
    e[a] += 1
    e[b] += 1

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

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

siz = [siz[i] - e[i] for i in range (1, n + 1)]

print (' '.join (list (map (str, siz))))

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind():
    def __init__(self, n):
        # uf.parentsで各ノードの親をリストで返す
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # uf.find(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):
        # uf.union(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):
        # uf.size(x)で処理を行う
        # 要素xが属するグループの要素数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # uf.same(x,y)で処理を行う
        # 要素x,yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # uf.members(x)で処理を行う
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # uf.roots()で処理を行う
        #　すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # uf.group_count()で処理を行う
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # all_group_members()で処理を行う
        # ｛ルート要素：[グループに属する要素のリスト]｝をdict型で返す
        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)
edge = [0]*(n+1)
anti_edge = [0]*(n+1)
for i in range(m):
    a,b = map(int,input().split())
    edge[a] += 1
    edge[b] += 1
    uf.union(a-1,b-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.same(c-1,d-1):
        anti_edge[c] += 1
        anti_edge[d] += 1
for i in range(n):
    size = uf.size(i)
    friend = edge[i+1]
    block = anti_edge[i+1]
    print(size-1-friend-block)

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind():
    def __init__(self, n):
        # uf.parentsで各ノードの親をリストで返す
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # uf.find(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):
        # uf.union(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):
        # uf.size(x)で処理を行う
        # 要素xが属するグループの要素数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # uf.same(x,y)で処理を行う
        # 要素x,yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # uf.members(x)で処理を行う
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # uf.roots()で処理を行う
        #　すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # uf.group_count()で処理を行う
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # all_group_members()で処理を行う
        # ｛ルート要素：[グループに属する要素のリスト]｝をdict型で返す
        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)
edge = []
anti_edge = [0]*(n+1)
for i in range(n+1):
    edge.append([])
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    uf.union(a-1,b-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.same(c-1,d-1):
        anti_edge[c] += 1
        anti_edge[d] += 1
for i in range(n):
    size = uf.size(i)
    friend = len(edge[i+1])
    block = anti_edge[i+1]
    print(size-1-friend-block)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

F = [[] for i in range(n)]   #Friend list
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    F[a].append(b)
    F[b].append(a)


gnum = 1    #group number
#DFS
def DFS_func(a:int, gnum:int):   #Target, Data
        if G[a] == 0:
            G[a] = gnum
            for i in range(len(F[a])):
                DFS_func(F[a][i], gnum)
        else:
            pass
G = [0 for i in range(n)]   #it has Group numbers       
for i in range(n):
    if G[i] == 0:
        DFS_func(i, gnum)
        gnum += 1
    else:
        pass

B = [0 for i in range(n)]   #How many Blocks in the same Group
for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if G[c] == G[d]:
        B[c] , B[d] = B[c]+1, B[d]+1
    else:
        pass

GS = [0 for i in range(gnum)]   #Group Size
for i in range(n):
    GS[G[i]] += 1

for i in range(n):
    if G[i] == 0:
        ans = 0
    else:
        ans = GS[G[i]]-len(F[i])-B[i]-1
    print(ans, end = ' ')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0] * (n+1)
        self.size = [1]*(n+1)

    # 検索
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        else:
            if self.size[x] < self.size[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]

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

    def cnt(self, x):
        # サイズの取得
        return self.size[self.find(x)]


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

union_find = UnionFind(n)
num_friends = [0]*(n+1)
num_block = [0]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    num_friends[a] += 1
    num_friends[b] += 1
    union_find.union(a, b)
# cd = [[_c, _d] for (_c, _d) in map(int, input().split())]
for i in range(k):
    # c[i], d[i] = map(int, input().split())
    c, d = map(int, input().split())
    if union_find.same_check(c, d):
        num_block[c] += 1
        num_block[d] += 1


num_suggest_friend = [0]*(n+1)  # 自分自身を引いておくので-1で初期化

for i in range(1, n+1):
    num_suggest_friend[i] = union_find.cnt(i) - \
        num_friends[i] - num_block[i] - 1

print(*num_suggest_friend[1:], sep=' ')

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M, K = map(int, input().split())

def dfs(v):
    size = 1
    for w in fr[v]:
        if ~roots[w]: continue
        roots[w] = roots[v]
        size += dfs(w)
    return size

fr = defaultdict(set)
for _ in range(M):
    a, b = [int(x) -1 for x in input().split()]
    fr[a].add(b)
    fr[b].add(a)
bl = defaultdict(set)
for _ in range(K):
    a, b = [int(x) - 1 for x in input().split()]
    bl[a].add(b)
    bl[b].add(a)

roots = [-1] * N
sizes = [-1] * N

for v in range(N):
    if ~roots[v]: continue
    roots[v] = v
    sizes[v] = dfs(v)

ans = []
for v in range(N):
    w = roots[v]
    res = sizes[w] - len(fr[v]) - sum(1 for u in bl[v] if roots[u] == w) -1
    ans.append(res)

print(*ans)