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(100000)
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


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

    # retrun the root of element x
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # unite the group include element x and group include element y
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # get size of the gourp which element x belongs
    def get_size(self, x):
        return -self.parents[self.find(x)]

    # check if element x and element y is same group
    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n, m, k = input_int_list()
    union = UnionFind(n + 1)
    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = input_int_list()
        friends[a].add(b)
        friends[b].add(a)
        union.unite(a, b)

    for j in range(k):
        a, b = input_int_list()
        # 同一グループでブロックしている人のみ記録する。
        if union.same(a, b):
            blocks[a].add(b)
            blocks[b].add(a)
    ans = []
    for i in range(1, n + 1):
        ans.append(union.get_size(i) - len(friends[i]) - len(blocks[i]) - 1)

    print(*ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M,K = map(int,input().split())
uf = UnionFind(N)
f_num = [0 for _ in range(N)] #友達の人数
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  uf.union(a,b)
  f_num[a] += 1; f_num[b] += 1
ans = [-1 for _ in range(N)]
for i in range(N):
  temp = uf.get_size(i) - (1+f_num[i])
  ans[i] = temp
for i in range(K):  
  c,d = map(int,input().split())
  c-=1;d-=1
  if uf.is_same(c,d): #嫌いな人が同じグループなら引く。
    ans[c] -= 1
    ans[d] -= 1
print(*ans,sep="\n")

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

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

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

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


n,m,k = map(int, input().split())
uf = UnionFind(n+1)
direct_cnts = [0]*(n+1)

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


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


ansl = []
for i in range(1,n+1):
    cnt = uf.size(i)-1
    cnt -= direct_cnts[i]
    for b in block[i]:
        if uf.same(i,b): cnt -= 1
    ansl.append(cnt)

print(*ansl)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
par=[0]*(N+1)
num=[0]*(N+1)
group = [1]*(N+1)

for i in range(1,N+1): par[i]=i

def root(x):
  if par[x]==x: return x
  return root(par[x])

def union(x,y):
  rx = root(x)
  ry = root(y)
  if rx==ry: return
  par[max(rx,ry)] = min(rx,ry)
  group[min(rx,ry)] += group[max(rx,ry)]

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

for _ in range(M):
  a,b=map(int,input().split())
  union(a,b)
  num[a]+=1
  num[b]+=1
for _ in range(K):
  c,d=map(int,input().split())
  if same(c,d):
    num[c]+=1
    num[d]+=1

for i in range(1,N+1):
  print(group[root(i)]-num[i]-1,end=" ")

Submission status: Accepted

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

par=[i for i in range(n)]
size=[1 for i in range(n)]


def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

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

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

for i in range(k):
    a,b=map(int,input().split())
    if find(a-1)==find(b-1):
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

ans=[]

for i in range(n):
    cnt=size[find(i)]
    xxx=list(set(graph[i]))
    cnt-=len(xxx)
    cnt-=1
    ans+=[str(cnt)]


print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

class UnionFind():
    
    # インデックスは0-start
    # 初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        self.group = n
    
    # private function
    def root(self, x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    # x,yが属するグループの結合
    def union(self, x, y):
        x = self.root(x)
        y = self.root(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
        self.group -= 1
    
    # x,yが同グループか判定
    def same(self, x, y):
        return self.root(x)==self.root(y)

    # xと同じグループの要素数を取得
    def size(self, x):
        return -self.parents[self.root(x)]
    
######################################################

N,M,K=mint()
T=UnionFind(N)
block=[0]*N
for _ in range(M):
    a,b=mint()
    T.union(a-1,b-1)
    block[a-1]+=1
    block[b-1]+=1
for _ in range(K):
    c,d=mint()
    if T.same(c-1,d-1):
        block[c-1]+=1
        block[d-1]+=1
ans=[T.size(i)-block[i]-1 for i in range(N)]
lprint(ans,' ')

Submission status: Accepted

Solution code:
# ABC157 D Friend Suggestions
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())
g = [[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-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):
        g[c-1].append(d-1)
        g[d-1].append(c-1)
        
ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i) - len(g[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.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]
UF = UnionFind(n)
f_or_b = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    UF.unite(a - 1, b - 1)
    f_or_b[a - 1] += 1
    f_or_b[b - 1] += 1
for i in range(k):
    c, d = map(int, input().split())
    if UF.same(c - 1, d - 1):
        f_or_b[c - 1] += 1
        f_or_b[d - 1] += 1
for i in range(n):
    print(UF.size(i) - f_or_b[i] - 1, end=" ")

Submission status: Accepted

Solution code:
#UnionFind
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())
V = [[] for i in range(n+1)]
W = [0]*(n+1)
uf = UnionFind(n+1)
for _ in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
    uf.union(a,b)
for _ in range(k):
    c,d = map(int,input().split())
    if uf.find(d) == uf.find(c):
        W[c] += 1
        W[d] += 1
    
for i in range(1,n+1):
    ans = uf.size(i) - len(V[i]) - W[i] - 1
    print(ans,end="")
    print(" ",end="")
print()

Submission status: Accepted

Solution code:
from collections import deque

n,m,k = map(int,input().split())
next = [[] for i in range(n)]
num_next= [0]*n
block = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  next[y-1].append(x-1)
  next[x-1].append(y-1)
  num_next[x-1] += 1
  num_next[y-1] += 1
  
for j in range(k):
  x,y = map(int,input().split())
  block[y-1].append(x-1)
  block[x-1].append(y-1)
friend = []
num = {}  
mark = ['t']*n
for i in range(n):
  if mark[i] == 't':
    
    mark[i] = i
    s = 1
    que = deque([i])
    while que:
      p = que.popleft()
      for x in next[p]:
        if mark[x] == 't':
          mark[x] = mark[p]
          s += 1
          que.append(x)
    num[i] = s      

ans = []
for i in range(n):
  l = num[mark[i]] -1-num_next[i]
  for y in block[i]:
    if mark[y] == mark[i]:
      l -= 1
  ans.append(str(l))    
      
print(' '.join(ans))

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 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)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])

Submission status: Accepted

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

f_adj_list = [[] for i in range(n)]
b_adj_list = [[] for i in range(n)]

for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  f_adj_list[_].append(__)
  f_adj_list[__].append(_)
  
for j in range(k):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  b_adj_list[_].append(__)
  b_adj_list[__].append(_)
  
  
group_id = [None for i in range(n)]
for i in range(n):
  if group_id[i] is not None: continue
  # i から DFS
  newly_visited = [i]
  group_id[i] = i
  while len(newly_visited) > 0:
    now = newly_visited.pop()
    for j in f_adj_list[now]:
      if group_id[j] is not None: continue
      newly_visited.append(j)
      group_id[j] = i

# group_id
# print(group_id)

# 連結成分のサイズ
from collections import Counter
cnt = Counter(group_id)
# cnt[5] = 7

ans_list = []
for i in range(n):
  ans = cnt[group_id[i]]
  ans -= 1 # 自分自身
  ans -= len(f_adj_list[i]) # 直接の友達
  for j in b_adj_list[i]:
    if group_id[i] == group_id[j]:
      ans -= 1
  ans_list.append(ans)

print(" ".join(map(str, ans_list)))

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n,m,k = map(int,stdin.readline().split())
    a = [list(map(int,stdin.readline().split())) for i in range(m)]
    c = [list(map(int,stdin.readline().split())) for i in range(k)]
    return n,m,k,a,c 

def main(n,m,k,a,c):
    #Compute all members' friends
    friends = [[] for i in range(n)]
    for i in a:
        friends[i[0]-1].append(i[1]-1)
        friends[i[1]-1].append(i[0]-1)
    
    #Group all members in the isolated "friend groups"
    frgroups = []
    visited = [False for i in range(n)]
    for i in range(n):
        if visited[i]:
            continue
        q = [i]
        temp = [i]
        visited[i] = True
        while q:
            idx = q.pop(0)
            adj = friends[idx]
            for j in adj:
                if visited[j]:
                    continue
                visited[j] = True
                q.append(j)
                temp.append(j)
        frgroups.append(temp)    

    #Number all members with their friend groups respectively
    groups = [-1 for i in range(n)]
    for i in range(len(frgroups)):
        for j in frgroups[i]:
            groups[j] = i 
            
    #For each member, refer to the friend groups of blocked peope
    #Compute ans accordingly
    ans = [len(frgroups[groups[i]])-1-len(friends[i]) for i in range(n)]
    for i in c:
        if groups[i[0]-1]==groups[i[1]-1]:
            ans[i[0]-1] -= 1
            ans[i[1]-1] -= 1
    s = str(ans[0])
    for i in range(1,n):
        s += " " + str(ans[i])
    print(s)
    

if __name__=="__main__":
    n,m,k,a,c = getval()
    main(n,m,k,a,c)

Submission status: Accepted

Solution code:
import collections
N, M, K = map(int, input().split())
friend = [[] for i in range(N)]
block = [[] for i in range(N)]
graph = [-1] * N
for i in range(M):
  a, b = map(int, input().split())
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
for i in range(K):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
#print(friend, block)

used = [True] * N
for i in range(N):
  if used[i]:
    q = [i]
    used[i] = False
    graph[i] = i
    while q:
      now = q.pop()
      for j in friend[now]:
        if used[j]:
          graph[j] = graph[now]
          q.append(j)
          used[j] = False
          
          
#print(graph)          
gg = dict(collections.Counter(graph))  
#print(gg)

for i in range(N):
  nn = graph[i]
  size = gg[nn]
  ans = size - 1
  for j in friend[i]:
    if nn == graph[j]:
      ans -= 1
  for j in block[i]:
    if nn == graph[j]:
      ans -= 1
  print(ans, end = " ")

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)

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

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

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

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

print(*ans)

Submission status: Accepted

Solution code:
class unionfind():

    def __init__(self,n):
        #親番号<0なら根
        #根の場合、数値の絶対値が要素数
        self.par=[-1 for i in range(n)]
        
    def root(self,x):
        
        par=self.par
        if par[x]<0:
            return x
        else:
            self.x = self.root(par[x])
            return self.x
        
    def unite(self,x,y):
        #高いほうに低いほうをくっつける
        rx=self.root(x)
        ry=self.root(y)
        
        if rx==ry:
            return
        else:
            if self.par[rx]>self.par[ry]:
                rx,ry = ry,rx
                
            self.par[rx]+=self.par[ry]
            self.par[ry] = rx

            
    def same(self, x,y):
        return self.root(x) == self.root(y)
    
    def par_print(self):
        print(self.par)
        
    def count(self, x):
        return -self.par[self.root(x)]

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

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

uf = unionfind(n)

for i in range(m):
    
    a,b = map(int,input().split())
    a-=1
    b-=1
    
    friend[a].append(b)
    friend[b].append(a)
    
    uf.unite(a,b)
    
    
    
for i in range(k):
    
    a,b = map(int,input().split())
    a-=1
    b-=1
    
    block[a].append(b)
    block[b].append(a) 
    
    
for i in range(n):
    
    ans = uf.count(i)-1 -len(friend[i])
    
    for j in block[i]:
        if uf.same(i,j):
            ans -= 1
    
    print(ans, end = " ")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, i):
        return -self.parent[self.root(i)]

    def roots(self):
        return [self.root(i) for i in range(self.N)]

    def groupcount(self):
        return len(set(self.roots()))

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

notfriend = [set() for _ in range(N)]
forest = UnionFind(N)

# friend
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    notfriend[a].add(b)
    notfriend[b].add(a)

    forest.unite(a, b)

# block
for i in range(K):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    if forest.same(a, b):
        notfriend[a].add(b)
        notfriend[b].add(a)

ans = ' '.join([str(forest.size(i) - 1 - len(notfriend[i])) for i in range(N)])
print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
root = [i for i in range(n)]
height = [1 for i in range(n)]
def find(n):
  sn = n
  while n != root[n]:
    n = root[n]
  root[sn] = n
  return n
def union(a,b):
  a = find(a)
  b = find(b)
  if a==b:
    return
  elif height[a]>=height[b]:
    height[a] += height[b]
    height[b] = 0
    root[b] = a
  else:
    height[b] += height[a]
    height[a] = 0
    root[a] = b
l = [set() for _ in range(n)]
for i in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  union(a,b)
  l[a].add(b)
  l[b].add(a)
for i in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  if find(a)==find(b):
    l[a].add(b)
    l[b].add(a)
print(*[height[find(i)]-len(l[i])-1 for i in range(n)])

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]





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

cnt=[1]*n
for i in range(n):
  cnt[i]=group_count(i)
  
check=[0]*n
for j in range(k):
  c,d=map(int,input().split())
  if same(c-1,d-1):
    check[c-1]+=1
    check[d-1]+=1
for i in range(n):
  print(cnt[i]-1-len(es[i])-check[i],end=" ")

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
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 = MI()
    uf = UnionFind(N)
    fri_list = [[]for _ in range(N)]
    blo_list = [[]for _ in range(N)]
    cnt_list = [0] * N
    for i in range(M):
        a, b = MI()
        a, b = a - 1, b - 1
        uf.union(a, b)
        fri_list[a].append(b)
        fri_list[b].append(a)
    for i in range(K):
        c, d = MI()
        c, d = c - 1, d - 1
        blo_list[c].append(d)
        blo_list[d].append(c)
    for i in range(N):
        cnt = uf.size(i)
        cnt -= len(fri_list[i]) + 1
        for b in blo_list[i]:
            if uf.same(i, b) == True:
                cnt -= 1
        cnt_list[i] = cnt
    print(' '.join(map(str, cnt_list)))


if __name__ == "__main__":
    main()