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.d = []
        for _ in range(n):
            self.d.append(-1)

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            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[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())
uf = UnionFind(n)
dame = [set() for _ in range(n)]

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

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

for i in range(n):
    ans = uf.size(i) - 1
    ans -= len(dame[i])
    print(ans, end=" ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [-1] * n
        # rank
        self.size = [1] * 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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

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

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

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
 
readline = sys.stdin.readline
n, m, k = map(int, readline().split())
# ab = [list(map(int, readline().split())) for i in range(m)]
# cd = [list(map(int, readline().split())) for i in range(k)]
 
friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
 
suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    # friend[b].append(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    # not_friend[d].append(c)
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)
 
for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = MAP()
A = [LIST() for i in range(M)]
C = [LIST() for i in range(K)]

tree = UnionFind(N)
block = defaultdict(list)
friend = defaultdict(list)

for a, b in A:
    tree.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

for c, d in C:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(N):
    block_num = 0
    for b in block[i]:
        # iを含む木の中にbが含まれているかどうか
        if tree.same(i, b):
            block_num += 1

    ans = tree.size(i) - 1 - len(friend[i]) - block_num
    print(ans, end=" ")
print()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
def root(x):
    while par[x]>=0:x=par[x]
    return x
def unite(x,y):
    x,y=root(x),root(y)
    if x!=y:
        if x>y:x,y=y,x
        par[x]+=par[y]
        par[y]=x
par=[-1]*n
def same(x,y):
    return root(x)==root(y)
def size(x):
  return-par[root(x)]
g=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    unite(a,b)
    g[a].append(b)
    g[b].append(a)
ss=[size(i)-len(g[i])-1 for i in range(n)]
for  i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if same(c,d):
        ss[c]-=1
        ss[d]-=1
print(*ss)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()


class UnionFind:
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rk = [0] * size

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rk[x] < self.rk[y]:
            self.par[x] = y
        elif self.rk[x] > self.rk[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            self.rk[y] += 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.unite(a, b)
    friend[a].add(b)
    friend[b].add(a)

block = defaultdict(set)
for _ in range(K):
    c, d = map(lambda x: int(x) - 1, input().split())
    block[c].add(d)
    block[d].add(c)

group = defaultdict(set)
for i in range(N):
    group[uf.find(i)].add(i)

ans = [0] * N
for people in group.values():
    for p in people:
        ans[p] = len(people) - 1 - sum(1 if i in people else 0 for i in friend[p]) - sum(1 if i in people else 0 for i in block[p])

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

Submission status: Accepted

Solution code:
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import sys
input = sys.stdin.readline

N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
 
uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1
 
L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)
 
for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1
 
ans = map(str, ans)
print(" ".join(ans))

Submission status: Accepted

Solution code:
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
 
uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1
 
L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)
 
for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1
 
ans = map(str, ans)
print(" ".join(ans))

Submission status: Accepted

Solution code:
class unionfind:
    def __init__(self,n): #準備
        self.par=[-1]*(n+1) #ノードは１スタート。各ノードの根を記録。自分が根のときは、-1
        
    def find(self,x): #ノードxの根を調べる
        if self.par[x]<0:
            return x #-1ではなく、根の番号を返す
        else:
            self.par[x]=self.find(self.par[x]) #経路圧縮。ノードxの根を再帰的に更新
            return self.par[x]
        
    def union(self,x,y): #併合
        x=self.find(x) #xの根
        y=self.find(y) 
        if x==y: #根が同じ
            return
        if self.par[y]<self.par[x]: #yのほうが、xよりサイズが大きいとき
            x,y=y,x
        #xのほうがサイズが大きくなるようにしてから、サイズの大きいxにyを併合。サイズが同じなら、どちらが根でも問題ない
        self.par[x]+=self.par[y]
        self.par[y]=x
        
                
    def same_check(self,x,y): #同じ集合に属するか判定
        return self.find(x)==self.find(y)
    
    def size(self,x):
        return -self.par[self.find(x)] #xの根のサイズ

n,m,k=map(int,input().split())
uf=unionfind(n)
kankei=[0]*(n+1) #0番目はなし
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a,b)
    kankei[a]+=1
    kankei[b]+=1
for i in range(k):
    c,d=map(int,input().split())
    if uf.same_check(c,d):
        kankei[c]+=1
        kankei[d]+=1
for i in range(1,n+1):
    print(str(uf.size(i)-kankei[i]-1),end=" ")

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    from collections import defaultdict
    from collections import deque

    N,M,K = LMIIS()
    AB = XLMIIS(M)
    CD = XLMIIS(K)
    edge = defaultdict(set)
    redge = defaultdict(set)
    blocks = defaultdict(set)
    
    for a,b in AB:
        # if a > b:
        #     a,b = b,a
        edge[a].add(b)
        #redge[b].add(a)
        edge[b].add(a)
    for c,d in CD:
        # if c > d:
        #     c,d = d,c
        blocks[c].add(d)
        blocks[d].add(c)
        #blocks[c][d] = False
        #blocks[d][c] = False

    visited = [False] * (N+1)
    
    num_graph = 0
    which_graph = [-1] * (N+1)
    num_grapth_node = [0] * N

    friends = deque()
    

    for i in range(1,N+1):
        if visited[i]:
            continue
        friends.append(i)
        while len(friends) > 0:
            node = friends.pop()
            if visited[node]:
                continue
            visited[node] = True
            which_graph[node] = num_graph
            num_grapth_node[num_graph] += 1
            for e in edge[node]:
                friends.append(e)
        num_graph+=1


    for i in range(1,N+1):
        num_friends = 0
        for f in edge[i]:
            if which_graph[i] == which_graph[f]:
                num_friends += 1
        num_blocks = 0
        for b in blocks[i]:
            if which_graph[i] == which_graph[b]:
                num_blocks += 1
        print(num_grapth_node[which_graph[i]] - num_friends - num_blocks -1)









    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, N):
    self.par=[i for i in range(N)]
    self.rank=[0 for _ in range(N)]
    self.size=[1 for _ in range(N)]
    
  def unite(self, x, y):
    x=self.getroot(x)
    y=self.getroot(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 united(self, x, y):
    return self.getroot(x)==self.getroot(y)
      
  def getroot(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.getroot(self.par[x])
      return self.par[x]

  def getsize(self, x):
    return self.size[self.getroot(x)]
  
def LN2NL(N, LN):
  out=[[] for _ in range(N)]
  M=len(LN)
  for i in range(M):
    out[LN[i][0]].append(LN[i][1])
    out[LN[i][1]].append(LN[i][0])
  return out

N, M, K=map(int, input().split())
UF=UnionFind(N+1)
AB=[list(map(int, input().split())) for _ in range(M)]
CD=[list(map(int, input().split())) for _ in range(K)]
ABNL=LN2NL(N+1, AB)
CDNL=LN2NL(N+1, CD)

for i in range(M):
  UF.unite(AB[i][0], AB[i][1])
  
ans=[UF.getsize(i)-len(ABNL[i])-1 for i in range(N+1)]
for i in range(1, N+1):
  for j in range(len(CDNL[i])):
    if UF.united(i, CDNL[i][j]):
      ans[i]-=1
      
print(*ans[1:])

Submission status: Accepted

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

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M,K = map(int,input().split())
Fr = [0]*N
FrKi = UnionFind(N)
Bl = defaultdict(list)

for i in range(M):
    A,B = map(int,input().split())
    A -=1
    B-=1
    Fr[A]+=1
    Fr[B]+=1
    FrKi.union(A,B)
    
for i in range(K):
    A,B = map(int,input().split())
    A-=1
    B-=1
    Bl[A].append(B)
    Bl[B].append(A)
    
Ans = [0]*N
#print(FrKi.par)
#print(Fr)
for i in range(N):
    tmp = -FrKi.par[FrKi.find(i)] - Fr[i] -1
    for j in Bl[i]:
        if FrKi.same_check(i,j):
            tmp -= 1
    Ans[i] = tmp
print(*Ans)

Submission status: Accepted

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x]) 
            return self.root[x]
    
    """木の合併"""
    def Union(self, x, y):
        #入力ノードの親を探索
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        #既に同じ木に所属する場合
        if (x==y):
            return 
        
        #異なる木に所属する場合 -> rnkから判断して合併する
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            #rnkが同じ(深さが同じ)場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    #辺(x,y)が橋の場合 : isSameGroup(self, x, y)=False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]     
    
    """木(非連結成分)の数を数える"""
    #全連結成分にするために必要な橋の本数は、cnt - 1
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]
    
    """xが属する集合の個数"""
    def Size(self, x):
        return -self.root[self.Find_Root(x)]

n,m,k = map(int,input().split())
uf = UnionFind(n)
num = [0]*(n+1)
for _ in range(m):
    a,b = map(int,input().split())
    num[a] += 1
    num[b] += 1
    uf.Union(a,b)
block_edge = [[] for _ in range(n+1)]
for _ in range(k):
    c,d = map(int,input().split())
    block_edge[c].append(d)
    block_edge[d].append(c)
for i in range(1, n+1):
    res = uf.Size(i) - num[i] - 1
    for e in block_edge[i]:
        if uf.isSameGroup(i,e):
            res -= 1
    print(res, end=' ')

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
par = [-1]*n
num = [0]*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)]

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

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

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

for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e, i):
            cnt -= 1
    print(cnt, end=' ')

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,m,k = mi()

nakama = [0] * n
d = UnionFind(n)
for i in range(m):
    a,b = mi()
    a -= 1
    b -= 1
    d.union(a,b)
    nakama[a] += 1
    nakama[b] += 1
teki =[[] for _ in range(n)]
for i in range(k):
    a,b = mi()
    a -= 1
    b -= 1
    teki[a].append(b)
    teki[b].append(a)
ans = [0] * n
for i in range(n):
    ans[i] = d.size(i) -1 -nakama[i]
    for j in teki[i]:
        if d.same(i,j):
            ans[i] -= 1
print(*ans)

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
#follow = [[False for i in range(N)] for j in range(N)]
follow = [[] for _ in range(N)]
labels = [-1 for _ in range(N)]
edges = [0 for _ in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A].append(B)
    follow[B].append(A)
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

c = 0
for i in range(N):
    if (labels[i] == -1):
        s = []
        s.append(i)
        labels[i] = c
        while(len(s) != 0):
            u = s.pop()
            for i in range(len(follow[u])):
                if (labels[follow[u][i]] == -1):
                    labels[follow[u][i]] = c
                    s.append(follow[u][i])
        c += 1

groupV = [0]*(c+1)
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
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
'''

class DSU:

	def __init__(self,n):
		self.n = n
		self.par = list(range(self.n))
		self.size = [1 for i in range(self.n)]

	def find(self,i):
		while(i != self.par[i]):
			self.par[i] = self.par[self.par[i]]
			i = self.par[i]
		return i

	def unite(self,a,b):
		par_a = self.find(a)
		par_b = self.find(b)
		if(par_a == par_b):
			return False
		else:
			if(par_a <= par_b):
				self.par[par_b] = par_a
				self.size[par_a] += self.size[par_b]
				self.size[par_b] = 0
			else:
				self.par[par_a] = par_b
				self.size[par_b] += self.size[par_a]
				self.size[par_a] = 0
			return True

	def same(self,a,b):
		return self.par[a] == self.par[b]

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

N,M,K = map(int, stdin.readline().rstrip().split())
dsu = DSU(N)
directFriends = [0]*N
for i in range(M):
	a,b = map(int, stdin.readline().rstrip().split())
	a -= 1
	b -= 1
	dsu.unite(a,b)
	directFriends[a] += 1
	directFriends[b] += 1

enemiesInSameComponent = [0]*N
for i in range(K):
	a,b = map(int, stdin.readline().rstrip().split())
	a -= 1
	b -= 1
	if(dsu.find(a) == dsu.find(b)):
		enemiesInSameComponent[a] += 1
		enemiesInSameComponent[b] += 1


candidates = [0]*N
for i in range(N):
	tot = dsu.size[dsu.find(i)]
	candidates[i] = tot - directFriends[i] - enemiesInSameComponent[i] - 1


# print('PAR:',dsu.par)
# print('SIZE:',dsu.size)
# print()
# print(directFriends)
# print()
print(*candidates)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(k)]

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.size(x) < self.size(y): x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parent[self.find(x)]
    
uf = UnionFind(n)
for a, b in ab: uf.unite(a, b)
ans = [uf.size(i)-1 for i in range(n)]

for a, b in ab:
    if uf.same(a, b): ans[a] -= 1; ans[b] -= 1
for c, d in cd:
    if uf.same(c, d): ans[c] -= 1; ans[d] -= 1

print(*ans)