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:
def makeRelation():
  visited=[False]*(N+1)
  g=0 # group
  for n in range(1,N+1):
    if visited[n]:
      continue
    q={n}
    D.append(set())
    while q:
      j=q.pop()
      for i in F[j]: # search for friend
        if not visited[i]:
          visited[i]=True
          q.add(i)
          D[g]|={i}
    g+=1
    
def main():
  makeRelation()
  #print(D)
  for g in D:
    for d in g:
      ans[d]=len(g) - len(F[d]) - len(g&B[d]) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[set() for n in range(N+1)]
  AB=[list(map(int, input().split())) for m in range(M)]
  for a,b in AB:
    F[a].add(b)
    F[b].add(a)
  B=[set() for n in range(N+1)]
  CD=[list(map(int, input().split())) for k in range(K)]
  for c,d in CD:
    B[c].add(d)
    B[d].add(c)
  D=[]
  #print(F)
  #print(B)
  ans=[0]*(N+1)
  main()

Submission status: Accepted

Solution code:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(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 union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        if self.par[x]>self.par[y]:
          x,y=y,x
          
        self.par[x]+=self.par[y]
        self.par[y]=x

    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def size(self,x):
      return -self.par[self.find(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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[0 for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1]+=1
  good[b-1]+=1
  
  
ans=[0  for _ in range(n)]
    
    
bad=[0 for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  if uf.same(p-1,q-1):
    
    bad[p-1]+=1
    bad[q-1]+=1


ans1=[]
for u in range(n):
  C=uf.size(u)
  
  ans1.append(str(C-1-bad[u]-good[u]))
  
print(' '.join(ans1))

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.par[x-1] += self.par[y-1]
            self.par[y-1] = x
        else:
            self.par[y-1] += self.par[x-1]
            self.par[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

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

    def count(self, x):
        return -self.par[self.find(x)-1]

from collections import deque

N,M,K=map(int,input().split())
U=UnionFind(N)
q=deque([])
for _ in range(M):
  a,b=map(int,input().split())
  U.union(a,b)
  deque.append(q,(a,b))
G=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=deque.pop(q)
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
for _ in range(K):
  a,b=map(int,input().split())
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
ans=[0]*N
for i in range(1,N+1):
  ans[i-1]=U.count(i)-len(G[i-1])-1
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
 
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)]
 
friend_g = [set() for i in range(N)]
for a, b in AB:
    a, b = a-1, b-1
    friend_g[a].add(b)
    friend_g[b].add(a)
friend_count = [len(s) for s in friend_g]
 
g_nums = [-1]*N
current_g_num = 0
for i in range(N):
    if g_nums[i] == -1:
        g_nums[i] = current_g_num
        q = [i]
        while q:
            t = q.pop()
            for friend in friend_g[t]:
                if g_nums[friend] == -1:
                    g_nums[friend] = current_g_num
                    q.append(friend)
                # print(i, t, g_nums)
        current_g_num += 1
 
block_count = [0]*N
for c, d in CD:
    c, d = c-1, d-1
    if g_nums[c] == g_nums[d]:
        block_count[c] += 1
        block_count[d] += 1
 
g_nums_counter = Counter(g_nums)
print(*(g_nums_counter[g_nums[i]] - friend_count[i] - block_count[i] - 1 for i in range(N)))

Submission status: Accepted

Solution code:
from collections import Counter
import sys

n, m, k = map(int, input().split())
F = [[] for _ in range(n)]
B = [[0] for _ in range(n)]

sys.setrecursionlimit(10**9)

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

rks = [0]*(n)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    for i in F[s]:
        if rks[i-1] != 0:
            continue
        dfs(i-1,r)

r = 0
for i in range(n):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

for _ in range(k):
    c, d = map(int, input().split())
    if rks[c-1] == rks[d-1]:
        B[c-1][0] += 1
        B[d-1][0] += 1

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(F[i]) - (B[i][0]) - 1)

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2*100)

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    stack = []
    color = {v: None for v in range(N)}
    col2v = {col: set() for col in range(N)}
    
    def dfs(j, col):
        if color[j] is not None:
            return
        # seen[j] = 1
        col2v[col] = set()
        stack.append(j)
        color[j] = col
        col2v[col].add(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if color[g_NO] is not None:
                continue
            color[g_NO] = col
            col2v[col].add(g_NO)
            # color[g_NO] = 1
            stack.append(g_NO)
    # def dfs(node, co):
    #     if color[node] is not None:
    #         return
        
    #     color[node] = co
    #     col2v[co].add(node)
    #     for n in G[node]:
    #         dfs(n, co)
    #     return
        
    c = 0
    for start in range(N):
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        # kouho = col2v[color[v]]
        # # print(kouho)
        # block = Block[v]
        # # print(block)
        # friend = G_original[v]
        # # print(friend)
        # tmp = kouho - set(block + friend)
        tmp = col2v[color[v]]
        tmp2 = tmp & set(Block[v])
        tmp3 = tmp & set(G_original[v])
        print((len(tmp)-len(tmp2)-len(tmp3)-1), end=" ")
        # ans.append(len(col2v[color[v]] - set(Block[v]+G_original[v]))-1)
        
        # print("##############")
    # print(*ans)
main()

Submission status: Accepted

Solution code:
from collections import Counter

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

friend_g = [set() for i in range(N)]
for a, b in AB:
    a, b = a-1, b-1
    friend_g[a].add(b)
    friend_g[b].add(a)
friend_count = [len(s) for s in friend_g]

g_nums = [-1]*N
current_g_num = 0
for i in range(N):
    if g_nums[i] == -1:
        g_nums[i] = current_g_num
        q = [i]
        while q:
            t = q.pop()
            for friend in friend_g[t]:
                if g_nums[friend] == -1:
                    g_nums[friend] = current_g_num
                    q.append(friend)
                # print(i, t, g_nums)
        current_g_num += 1

block_count = [0]*N
for c, d in CD:
    c, d = c-1, d-1
    if g_nums[c] == g_nums[d]:
        block_count[c] += 1
        block_count[d] += 1

g_nums_counter = Counter(g_nums)
print(*(g_nums_counter[g_nums[i]] - friend_count[i] - block_count[i] - 1 for i in range(N)))

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        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,y=self.find(x),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())
uf=UnionFind(N+1)
n_friends=defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  uf.unite(a,b)
  n_friends[a] += 1
  n_friends[b] += 1
  
ans = [uf.size(i)-n_friends[i]-1 for i in range(N+1)]

for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c,d):
    ans[c] -= 1
    ans[d] -= 1
  
print(*ans[1:])

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

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 solve():
    N, M, K = MAP()
    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]

    uf = UnionFind(N) # 初期化

    for i in range(M):
        a, b = MAP()
        F[a-1].append(b-1)
        F[b-1].append(a-1)
        uf.union(a-1, b-1) # グループを併合

    for i in range(K):
        c, d = MAP()
        B[c-1].append(d-1)
        B[d-1].append(c-1)

    for i in range(N):
        ans = uf.size(i) - len(F[i]) - 1
        for x in B[i]:
            if uf.same(i, x):
                ans -= 1
        print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        # self.group_num = 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 get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def is_same(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.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        # self.group_num -= 1

n, m, k = LI()
U = UnionFind(n)
G1 = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G1[a - 1] += [b - 1]
    G1[b - 1] += [a - 1]
    U.union(a - 1, b - 1)

G2 = [[] for _ in range(n)]
for _ in range(k):
    c, d = LI()
    G2[c - 1] += [d - 1]
    G2[d - 1] += [c - 1]

for i in range(n):
    ret = U.get_size(i) - 1 - len(G1[i])
    for j in G2[i]:
        if U.is_same(i, j):
            ret -= 1
    print(ret, end=" ")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n
 
    def find(self, 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):
        #要素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):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
 
    def members(self, x):
        # 要素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())
u = UnionFind(n)
ans = [0]*n

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

for i in range(n):
    ans[i] += u.size(i) - 1

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

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
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())
block = [0]*n
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)

uf.find(0)
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

ans = [uf.size(i) - block[i] - 1 for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
import sys

rl=lambda:next(sys.stdin)
rfs=lambda:rl().split()
ris=lambda:map(int,rfs())

N,M,K=ris()

adj=[{*()} for _ in range(N)]
for _ in range(M):
    A,B=ris()
    A,B=A-1,B-1
    adj[A].add(B)
    adj[B].add(A)

c=-1
cs=[c]*N
ct={}
for u in range(N):
    if cs[u]!=-1:
        continue
    c+=1
    cs[u]=c
    stk=[u]
    while stk:
        u=stk.pop()
        if c not in ct:
            ct[c]=0
        ct[c]+=1
        for v in adj[u]:
            if cs[v]!=-1:
                continue
            cs[v]=c
            stk.append(v)

ans=[0]*N
for u in range(N):
    g=ct[cs[u]]-1
    f=len(adj[u])
    ans[u]=g-f

for _ in range(K):
    A,B=ris()
    A,B=A-1,B-1
    if cs[A]==cs[B]:
        ans[A]-=1
        ans[B]-=1

print(*ans)

Submission status: Accepted

Solution code:
import sys

ris=lambda:map(int,next(sys.stdin).split())

N,M,K=ris()

adj=[set() for _ in range(N)]
for _ in range(M):
    A,B=ris()
    A,B=A-1,B-1
    adj[A].add(B)
    adj[B].add(A)

colors=[-1]*N
ct={}
color=-1
for u in range(N):
    if colors[u]!=-1:
        continue
    color+=1
    colors[u]=color
    stk=[u]
    while stk:
        u=stk.pop()
        ct[color]=ct.get(color,0)+1
        for v in adj[u]:
            if colors[v]==-1:
                colors[v]=color
                stk.append(v)

blk=[{*()} for _ in range(N)]
for _ in range(K):
    A,B=ris()
    A,B=A-1,B-1
    if colors[A]==colors[B]:
        blk[A].add(B)
        blk[B].add(A)

ans=[0]*N
for u in range(N):
    c=colors[u]
    g=len(adj[u])
    b=len(blk[u])
    k=ct[c]-1-g-b
    ans[u]=k

print(*ans)

Submission status: Accepted

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

adj=[set() for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    adj[A].add(B)
    adj[B].add(A)

blk=[{*()} for _ in range(N)]
for _ in range(K):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    blk[A].add(B)
    blk[B].add(A)

#print(adj)
#print(blk)

colors=[-1]*N
ct={}
color=-1
for u in range(N):
    if colors[u]!=-1:
        continue
    color+=1
    colors[u]=color
    stk=[u]
    while stk:
        u=stk.pop()
        ct[color]=ct.get(color,0)+1
        for v in adj[u]:
            if colors[v]==-1:
                colors[v]=color
                stk.append(v)


ans=[0]*N
for u in range(N):
    c=colors[u]
    k=ct[c]-1-len(adj[u])
    for v in blk[u]:
        if colors[v]==c:
            k-=1
    ans[u]=k

print(*ans)

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

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


################################
N, M, K = map(int, input().split())
uf = UnionFind(N + 1)
friends = [set() for _ in range(N + 1)]
blocks = [set() for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
    uf.union(a, b)

for _ in range(K):
    c, d = map(int, input().split())
    blocks[c].add(d)
    blocks[d].add(c)

ans = []

for i in range(1, N + 1):
    group_size = uf.size(i)
    friend_cnt = len(friends[i])
    block_cnt = 0
    for j in blocks[i]:
        if uf.same(i, j):
            block_cnt += 1
    suggest_cnt = group_size - friend_cnt - block_cnt - 1
    ans.append(suggest_cnt)

print(*ans)

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

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

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

tree = UnionFind(N)
friends = [set() for i in range(N)]
blocks = [set() for i in range(N)]

for i in range(M):
    a, b = list(map(int, input().split()))
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)
    tree.union(a-1, b-1)

for i in range(K):
    c, d = list(map(int, input().split()))
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)

cnt = []

for i in range(N):
    group_size = tree.size(i)
    friend_cnt = len(friends[i])
    block_cnt = len([j for j in blocks[i] if tree.same(i, j)])
    cnt.append(group_size - friend_cnt - block_cnt - 1)

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

Submission status: Accepted

Solution code:
from collections import *
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(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 
        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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
d=[0]*(n+1)
for _ in [0]*m:
  a,b=map(int,input().split())
  d[a]+=1
  d[b]+=1
  uf.unite(a,b)
to=[[]for _ in [0]*(n+1)]
for _ in [0]*k:
  a,b=map(int,input().split())
  to[a]+=[b]
  to[b]+=[a]
a=[]
b=dict(Counter([uf.find(i) for i in range(1,n+1)]))
for i,j in enumerate(d):
  if i==0:continue
  ans=b[uf.find(i)]-j-1
  for k in to[i]:
    if uf.same(i,k):ans-=1
  a+=[ans]
print(*a)

Submission status: Accepted

Solution code:
from collections import deque

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

f = [set() for _ in range(N + 1)]
b = [set() for _ in range(N + 1)]

for _ in range(M):
    f1, f2 = map(int, input().split())
    f[f1].add(f2)
    f[f2].add(f1)

for _ in range(K):
    b1, b2 = map(int, input().split())
    b[b1].add(b2)
    b[b2].add(b1)


dq = deque()
ans = [0] * (N + 1)
visited = [False] * (N + 1)

for i in range(1, N + 1):

    # iを含む連結リストが既に作られている場合はスキップ
    if visited[i]:
        continue

    # setは{}で書く、後で積集合が楽に取れる
    link = {i}
    dq.append(i)
    visited[i] = True

    # DFS
    while dq:
        n = dq.pop()
        # nのフレンド全員について
        for j in f[n]:
            # まだ訪れていないノードの場合
            if not visited[j]:
                link.add(j)
                dq.append(j)
                visited[j] = True

    for user in link:
        # 全体-既にフレンドの人数-ブロックした人数-自分自身
        # set同士で積集合をとる
        ans[user] = len(link) - len(link & f[user]) - len(link & b[user]) - 1

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(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())

n,m,k=mp()
uf=UnionFind(n+1)
fr=[[] for i in range(n+1)]
br=[[] for i in range(n+1)]
for i in range(m):
    a,b=mp()
    fr[a].append(b)
    fr[b].append(a)
    uf.union(a,b)
for i in range(k):
    c,d=mp()
    br[c].append(d)
    br[d].append(c)
ans=[]
for i in range(1,n+1):
    c=uf.size(i)-len(fr[i])
    for j in br[i]:
        if uf.same(i,j):
            c-=1
    ans.append(c-1)
print(*ans)