Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

import sys
input=sys.stdin.readline
n,m,k = map(int, input().split())
f_link = [[] for _ in range(n)]
uf = UnionFind(n)
for i in range(m):
    tmp = list(map(int,input().split()))
    f_link[tmp[0]-1].append(tmp[1]-1)
    f_link[tmp[1]-1].append(tmp[0]-1)
    uf.union(tmp[0]-1,tmp[1]-1)
b_link = [[] for _ in range(n)]
for i in range(k):
    tmp = list(map(int,input().split()))
    b_link[tmp[0]-1].append(tmp[1]-1)
    b_link[tmp[1]-1].append(tmp[0]-1)

ans=[]
for i in range(n):
    fnum=len(f_link[i])
    bnum=len(b_link[i])
    f_cand=uf.size(i)
    b_f_num=0
    for j in b_link[i]:
        if uf.same(i,j):
            b_f_num+=1
    ans.append(f_cand-fnum-b_f_num-1)
print(*ans)

Submission status: Accepted

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

n,m,k = map(int,input().split())
graph = {i+1:[] for i in range(n)}
block = {i+1:[] for i in range(n)}
ans = [-1 for _ in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
for _ in range(k):
  c,d = map(int,input().split())
  block[c].append(d)
  block[d].append(c)
  
  
from collections import deque

for i in range(1,n+1):
  if ans[i-1] != -1:
    continue
  queue = deque([i])
  friends = set([i])
  while queue:
    node = queue.popleft()
    for n in graph[node]:
      block[node].append(n)
      if n in friends:
        continue
      friends.add(n)
      queue.append(n)
  for n in friends:
    ans[n-1] = len(friends)-1 #remove self
    for b in set(block[n]):
      if b in friends:
        ans[n-1] -= 1
    
    
print(*ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.cnt = [1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.cnt[r1]+=self.cnt[r2]
            if d1 == d2:
                self.table[r1] -= 1
                
        else:
            self.table[r1] = r2
            self.cnt[r2]+=self.cnt[r1]
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)

show_flg=False
show_flg=True

n,m,k=LI()

g=[[] for i in range(n)]
bl=[[] for i in range(n)]

#g,_=GI(n,m)
uf=UnionFind(n)
for i in range(m):
    a,b=LI_()
    uf.union(a,b)
    g[a]+=[b]
    g[b]+=[a]

for i in range(k):
    c,d=LI_()
    bl[c].append(d)
    bl[d].append(c)

A=[]
for i in range(n):
    fg=uf._root(i)
    ans=uf.cnt[fg]-1
    blk=0
    for e in bl[i]:
        if fg==uf._root(e):
            blk+=1
    A+=[ans-blk-len(g[i])]

print(*A)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

from collections import defaultdict
def main():
    N, M, K = map( int, input().split())
    AB = [ tuple( map( lambda x:x-1, map( int, input().split()))) for _ in range(M)]
    CD = [ tuple( map( lambda x:x-1, map( int, input().split()))) for _ in range(K)]
    fn = [0]*N
    bn = [0]*N
    df = defaultdict( lambda : False)
    friends = [ i for i in range(N)]
#    blocks = [ i for i in range(N)]
    for a, b in AB:
        fn[a] += 1
        fn[b] += 1
        df[(a,b)] = True
        df[(b,a)] = True
        union(friends,a,b)
    for c, d in CD:
#        union(blocks, c, d)
        if find(friends, c) == find( friends, d):
            if not df[(c,d)]:
                bn[c] += 1
                bn[d] += 1
    S = [-1]*N
    for i in range(N):
        S[ find( friends, i)] += 1
    ANS = [0]*N
    for i in range(N):
        ANS[i] = S[ find( friends, i)] - fn[i] - bn[i]
    print(' '.join( map( str, ANS)))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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


class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [1] * size
        self.groups = size

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root  # 同じnodeへの2回目以降のget_rootを高速にするために、直接rootに繋いでおく
        return root

    def in_same_group(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1 == root2

    def unite(self, node1, node2):
        if self.in_same_group(node1, node2):
            return
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if self.rank[main_root] < self.rank[sub_root]:  # rankの大きい方をmain_rootにする
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


n, m, k = map(int, input().split())
uf = UnionFind(n)
minus_count = [1] * n
# friend
for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)
    minus_count[a-1] += 1
    minus_count[b-1] += 1

for _ in range(k):
    a, b = map(int, input().split())
    if uf.in_same_group(a-1, b-1):
        minus_count[a-1] += 1
        minus_count[b-1] += 1

result = []
for i in range(n):
    parent = uf.get_root(i)
    count = uf.rank[parent]
    ans = count - minus_count[i]
    result.append(ans)

print(*result)

Submission status: Accepted

Solution code:
class uni:
    def __init__(self,n):
        self.n = n
        self.pare = [i for i in range(n)]
        self.rank = [0]*n

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

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

    def show(self):
        return self.pare


N, M, K = map(int,input().split())
size = [0]*N
count = [0]*N
side = [[]for i in range(N)]
union = uni(N)
for i in range(M):
    a,b = map(int,input().split())
    union.union(a-1,b-1)
    count[a-1] += 1
    count[b-1] += 1
for i in range(N):
    size[union.find(i)] += 1
for i in range(K):
    c,d = map(int,input().split())
    if union.pare[c-1] == union.pare[d-1]:
        count[c-1] += 1
        count[d-1] += 1
for i in range(N):
    print(size[union.pare[i]]-count[i]-1,end=" ")
print()

Submission status: Accepted

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

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

    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 merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.num[y] += self.num[x]
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.num[x] += self.num[y]
        else:
            self.parent[x] = y
            self.rank[y] += 1
            self.num[y] += self.num[x]

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


block = [0] * n
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.find(c) == uf.find(d):
        block[c] += 1
        block[d] += 1

ans = [0] * n
for i in range(n):
    ans[i] = uf.num[uf.find(i)]-1 - friend[i] - block[i]
print(*ans)

Submission status: Accepted

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

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)

  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

def Same(x, y, par):
  return Find(x, par) == Find(y, par)

def Size(x, par):
  return -par[Find(x, par)]

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

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

cnt1 = [0]*n
cnt2 = [0]*n
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    Unite(a, b, par, rank)
    cnt1[a] += 1
    cnt1[b] += 1
for j in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if Same(c, d, par):
        cnt2[c] += 1
        cnt2[d] += 1

#print(par)
#print(cnt1)
#print(cnt2)
anss = [0]*n
for i in range(n):
    ans = Size(i, par) -1 - cnt1[i] - cnt2[i]
    #print(max(ans, 0))
    anss[i] = max(ans, 0)
print(*anss)

Submission status: Accepted

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


# aとbの友人候補
# aとbはブロックされてないけど友達でもない
# かつ直接友人じゃないけど友人同士でつながっているのは友人候補である。


# まず友達関係のdisjoint setを求めておく
# あるdisjoint setにおいて、全員が友達候補であると仮定しておく。すでに友達である人数を引く。さらにブロック関係の人数も引く。()

from collections import defaultdict
N, M, K = read_ints()
uf = UnionFind(N)
direct_friends = defaultdict(lambda: 0)
for m in range(M):
    a, b = read_ints()
    direct_friends[a - 1] += 1
    direct_friends[b - 1] += 1
    uf.unite(a - 1, b - 1)

# まって、ブロックだけど、同じunionにあるブロック数だけカウントしたい
block = defaultdict(lambda: 0)
for m in range(K):
    a, b = read_ints()
    if uf.is_in_same(a - 1, b - 1):
        block[a - 1] += 1
        block[b - 1] += 1


ans = []
for i in range(N):
    katei = uf.size(i) - 1
    katei -= direct_friends[i]
    katei -= block[i]
    ans.append(katei)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_

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

node_list = [UnionFindNode(i) for i in range(N)]

friend_num = [0] * N
for i in range(M):
    A,B = map(int,input().split())
    friend_num[A-1] += 1
    friend_num[B-1] += 1
    node_list[A-1].unite(node_list[B-1])

ans_array = [node.get_size() - friend - 1 for friend,node in zip(friend_num,node_list)]

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

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

Submission status: Accepted

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.e_num = [1 for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,x,y):
        if self.root(x) == self.root(y):
            return
        else:
            rootx = self.root(x)
            rooty = self.root(y)

            e_sum = self.e_num[rootx] + self.e_num[rooty]

            if self.rank[rootx] < self.rank[rooty]:
                self.par[rootx] = rooty
                self.e_num[rooty] = e_sum
            else:
                self.par[rooty] = rootx
                self.e_num[rootx] = e_sum

                if self.rank[rootx] == self.rank[rooty]:
                    self.rank[rootx] += 1

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

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


n,m,k = map(int,input().split())
num_rels = [0 for i in range(n)]
tree =uf_tree(n)

for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    tree.unite(a,b)
    # print(tree.e_num)
    num_rels[a] += 1
    num_rels[b] += 1

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

# print(num_rels)
#
# for i in range(n):
#     print(tree.e_num[tree.root(i)],end=" ")
# print()

for i in range(n):
    temp = tree.e_num[tree.root(i)]-1-num_rels[i]
    if temp >= 0:
        print(temp,end=" ")
    else:
        print(0,end=" ")
print()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,m,k=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
cd=[list(map(int,input().split())) for i in range(k)]
frnd=[0]*n
for i in range(m):
    a,b=ab[i]
    frnd[a-1]+=1
    frnd[b-1]+=1
blck={}
for i in range(k):
    c,d=cd[i]
    if not c in blck:
        blck[c]=[d]
    else:
        blck[c].append(d)
    if not d in blck:
        blck[d]=[c]
    else:
        blck[d].append(c)

# print(frnd)
# print(blck)

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
uf = WeightedUnionFind(n)
for i in range(m):
    a,b=ab[i]
    uf.union(a,b,1)
for i in range(n):
    uf.find(i+1)

cnt=dict(Counter(uf.par))
# print(uf.par)

anslst=[0]*n
for i in range(n):
    anslst[i]=cnt[uf.find(i+1)]-frnd[i]-1
    if i+1 in blck:
        for j in blck[i+1]:
            if uf.same(i+1,j):
                anslst[i]-=1
# print(cnt)
# print(frnd)
print(*anslst)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n, m, k = map(int, input().split())
uf = UnionFind(n)
from collections import defaultdict
block = defaultdict(int)
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    block[a-1] -= 1
    block[b-1] -= 1
    uf.union(a-1, b-1)

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

for i in range(n):
    print(uf.size(i) + block[i] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind(object):
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}
        self.size = {i: 1 for i in range(n)}
    
    def find(self, x):
        if self.parent[x] != x:
            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
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y

        else:
            self.parent[y] = x

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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


n, m, k = map(int, input().split())
As, Bs = list(), list()
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    As.append(a)
    Bs.append(b)

edge_friends = defaultdict(list)
for a, b in zip(As, Bs):
    edge_friends[a].append(b)
    edge_friends[b].append(a)

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

union_find = UnionFind(n)
for a, b in zip(As, Bs):
    union_find.union(a, b)

counts = list()
for i in range(n):
    parent = union_find.find(i)
    n_blocks = 0
    for node in edge_block[i]:
        if parent == union_find.find(node):
            n_blocks += 1
    n_friends = 0
    for node in edge_friends[i]:
        if parent == union_find.find(node):
            n_friends += 1

    count = union_find.get_size(i) - 1 - n_blocks - n_friends
    counts.append(count)

print(*counts)

Submission status: Accepted

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

n,m,k = map(int, input().split())
net = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    net[a].append(b)
    net[b].append(a)

blocks = [ tuple(map(int, input().split())) for _ in range(k)]
id_to_group = {}
groups = []
num_candid = [0] * (n+1)

group_id = -1
for start in range(1, n+1):
    if start in id_to_group:
        continue
    group_id += 1
    # search connected component
    group = set()
    stack = [start]
    group.add(start)
    id_to_group[start] = group_id

    while stack:
        node = stack.pop()
        for nb in net[node]:
            if nb in id_to_group:
                continue
            group.add(nb)
            id_to_group[nb] = group_id
            stack.append(nb)
    for member in group:
        num_candid[member] = len(group) - 1 - len(net[member])

# deal with blcok
for a,b in blocks:
    if id_to_group[a] == id_to_group[b]:
        num_candid[a] -= 1
        num_candid[b] -= 1

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

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
CD = [tuple(map(int,input().split())) for i in range(K)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

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

friends = [0] * N
uf = UnionFind(N)
for a,b in AB:
    a,b = a-1,b-1
    friends[a] += 1
    friends[b] += 1
    if uf.is_same(a,b): continue
    uf.unite(a,b)
for i in range(N):
    uf.root(i)

from collections import Counter
ctr = Counter()
for i in range(N):
    r = uf.root(i)
    ctr[r] += 1

ans = []
for i in range(N):
    tmp = ctr[uf.root(i)] - 1 - friends[i]
    for b in blocks[i]:
        if uf.is_same(i,b):
            tmp -= 1
    ans.append(tmp)
print(*ans)

Submission status: Accepted

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

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

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

vst = [0] * N
SIZE = []
C = 0
for i in range(N):
    if not vst[i]:
        C += 1
        vst[i] = C
        q = [i]
        cnt = 0
        for u in q:
            cnt += 1
            for v in friend[u]:
                if not vst[v]:
                    vst[v] = C
                    q.append(v)
        SIZE.append(cnt)

for i in range(N):
    ret = SIZE[vst[i] - 1] - 1
    ret -= len(friend[i])
    for b in block[i]:
        if vst[i] == vst[b]:
            ret -= 1
    print(ret, end=' ')
print()