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 unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(
                4,
                [
                    [2, 1],
                    [1, 3],
                    [3, 2],
                    [3, 4],
                ],
                [
                    [4, 1]
                ]
            ),
            [0, 1, 0, 1]
        )

    def test_2(self):
        self.assertEqual(
            think(
                5,
                [
                    [1, 2],
                    [1, 3],
                    [1, 4],
                    [1, 5],
                    [3, 2],
                    [2, 4],
                    [2, 5],
                    [4, 3],
                    [5, 3],
                    [4, 5],
                ],
                [
                ]
            ),
            [0, 0, 0, 0, 0]
        )

    def test_3(self):
        self.assertEqual(
            think(
                10,
                [
                    [10, 1],
                    [6, 7],
                    [8, 2],
                    [2, 5],
                    [8, 4],
                    [7, 3],
                    [10, 9],
                    [6, 4],
                    [5, 8],
                ],
                [
                    [2, 6],
                    [7, 5],
                    [3, 1],
                ]
            ),
            [1, 3, 5, 4, 3, 3, 3, 3, 1, 0]
        )


def solve():
    n, list_of_a_and_b, list_of_c_and_d = read()
    result = think(n, list_of_a_and_b, list_of_c_and_d)
    write(result)


def read():
    n, m, k = read_int(3)
    list_of_a_and_b = []
    for _ in range(m):
        a, b = read_int(2)
        list_of_a_and_b.append([a, b])
    list_of_c_and_d = []
    for _ in range(k):
        c, d = read_int(2)
        list_of_c_and_d.append([c, d])
    return n, list_of_a_and_b, list_of_c_and_d


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, list_of_a_and_b, list_of_c_and_d):
    adjacency_list_of_friend = make_adjacency_list_from(n, list_of_a_and_b)
    adjacency_list_of_block = make_adjacency_list_from(n, list_of_c_and_d)
    list_of_connected_graph = collect_connected_graph_from(n, adjacency_list_of_friend)
    candidate_of_friends = [0] * n
    for connected_graph in list_of_connected_graph:
        for vertex in connected_graph:
            index = vertex - 1
            candidate_of_friends[index] = len(connected_graph)
            candidate_of_friends[index] -= len(adjacency_list_of_friend[vertex])
            for blocked in adjacency_list_of_block[vertex]:
                if blocked in connected_graph:
                    candidate_of_friends[index] -= 1
            candidate_of_friends[index] -= 1
    return candidate_of_friends


def write(result):
    print(' '.join(map(str, result)))


def make_adjacency_list_from(n, list_of_pair):
    adjacency_list = {}
    for i in range(1, n + 1):
        adjacency_list[i] = []
    for left, right in list_of_pair:
        adjacency_list[left].append(right)
        adjacency_list[right].append(left)
    return adjacency_list


def collect_connected_graph_from(n, adjacency_list):
    visited = [False for _ in range(n + 1)]
    list_of_connected_graph = []
    for vertex in range(1, len(visited)):
        if visited[vertex]:
            continue
        connected_graph = set([vertex])
        queue = collections.deque([vertex])
        while queue:
            data = queue.popleft()
            if visited[data]:
                continue
            visited[data] = True
            connected_graph.add(data)
            for next_data in adjacency_list[data]:
                queue.append(next_data)
        list_of_connected_graph.append(connected_graph)
    return list_of_connected_graph


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
n,m,k=[int(j) for j in input().split()]
par=[-1 for i in range(n)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True


f=set(tuple(int(j)-1 for j in input().split()) for _ in range(m))
b=set(tuple(int(j)-1 for j in input().split()) for _ in range(k))

for a in f:
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

ans=[]
for i in range(n):
    ans.append(-par[root(i)]-1)

for i,j in f:
    if root(i)==root(j):
        ans[i]-=1
        ans[j]-=1
for i,j in b:
    if root(i)==root(j):
        ans[i]-=1
        ans[j]-=1

print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter

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


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

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if self.rank[x] > self.rank[y]:
            self.parent[root_y] = root_x
        elif self.rank[x] < self.rank[y]:
            self.parent[root_x] = root_y
        elif root_x != root_y:
            self.parent[root_y] = root_x
            self.rank[x] += 1
        pass


uf = UnionFind(N)

for a, b in AB:
    uf.unite(a - 1, b - 1)

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

print(*ans)

Submission status: Accepted

Solution code:
# 小さい方の木を大きい方にくっつける O(logN)
# 経路縮約(メモ化) ならしO(logN)
# 両方やると、ならしO(α(N)) α: カルマン関数

# 実装
# 子: 親のID, 根: -サイズ (非負: 子, 負: 根)
# atcoder ABC 158 解説に詳細
class UnionFind():

    def __init__(self, n=0):
        self.d = [-1 for _ in range(N)] # 経路縮約のためのメモ
    
    def find(self, x): # xが所属するグループの親を返す
        if self.d[x]<0:
            return x
        res = self.find(self.d[x])
        self.d[x] = res # 経路縮約の箇所
        return res
    
    def unite(self, x, y): # x, yが所属するグループを結合する, 結合に成功したらTrue, すでに結合していたらFalse
        # まずx, yをそれぞれの親にする
        x = self.find(x)
        y = self.find(y) 
        if x==y:
            return False
        # xの方が大きい木になるようにする (サイズは負であることに注意)
        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): # xが所属しているグループのサイズを返す
        return -self.d[self.find(x)]

N, M, K=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
CD=[list(map(int, input().split())) for _ in range(K)]

uf = UnionFind(N)
deg = [0 for _ in range(N)] # 友達関係にある人の個数(グラフにおける各頂点の次数)を保持
to = [[] for _ in range(N)] # ブロック関係にある人に枝を張る

# 友達関係
for i in range(M):
    a, b = AB[i]
    a-=1
    b-=1
    deg[a]+=1
    deg[b]+=1
    uf.unite(a, b)
# ブロック関係
for i in range(K):
    c, d = CD[i]
    c-=1
    d-=1
    to[c].append(d)
    to[d].append(c)
# 答え
ans=[0 for _ in range(N)]
for i in range(N):
    # 各人(頂点)の所属するグループのサイズから、自分自身と、直接の友達関係を引く
    ans[i]=uf.size(i)-1-deg[i]
    # 各人のブロック関係にある人が同じグループに所属している場合は、答えを-する
    for u in to[i]:
        if uf.same(i, u):
            ans[i]-=1
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n,m,k = list(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)]

from bisect import bisect_left

#unifind木の実装

class UniFindTree():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size_of_group = [0] * n
    def find_root(self,i):
        if self.par[i]==i:
            #if root
            return i
        else:
            self.par[i] = self.find_root(self.par[i])
            return self.par[i]

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x]=y
        else:
            self.par[y] = x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same(self,x,y):
        return self.find_root(x)==self.find_root(y)
    def set_size_of_group(self):
        for i in self.par:
            self.size_of_group[i]+=1
    def shukuyaku(self):
        for i in range(len(self.par)):
            self.find_root(i)
uni = UniFindTree(n+1)
for a,b in ab:
    uni.unite(a,b)
uni.shukuyaku()
uni.set_size_of_group()
ret = [uni.size_of_group[i]-1 for i in uni.par]
for a,b in ab:
    if uni.same(a,b):
        ret[a]-=1
        ret[b]-=1

for c,d in cd:
    if uni.same(c,d):
        ret[c]-=1
        ret[d]-=1

print(" ".join(map(str,ret[1::])))

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

blist=[]
for i in range(K):
  c,d=map(int,input().split())
  blist.append((c,d))
  
#print(fdic)
#print(blist)

dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      #print(new_queue)
      
#print(cluster_list)
#print(dic_cluster)

candlist=[0]*(N+1)
for i in range(1,N+1):
  candlist[i]=len(dic_cluster[cluster_list[i]])-len(fdic[i])-1
for c,d in blist:
  if d in dic_cluster[cluster_list[c]]:
    candlist[c]-=1
    candlist[d]-=1
  
print(" ".join(map(str,candlist[1:])))

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        #print(ai, bi, S)

    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        if same(ai, bi):
            T[ai] += 1
            T[bi] += 1
    #print(S)
    #print(T)

    ans = [size(i) - T[i] for i in range(N)]
    print(*ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        #print(ai, bi, S)

    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        if same(ai, bi):
            T[ai] += 1
            T[bi] += 1
    #print(S)
    #print(T)

    ans = [size(i) - T[i] for i in range(N)]
    print(*ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        #print("j", ai, aj)
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        #print(ai, bi, S)

    U = [set() for i in range(N)]
    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        U[ai].add(bi)
        U[bi].add(ai)
    #print(S)
    #print(T)

    ans = [size(i) - T[i] - sum(same(i, j) for j in U[i]) for i in range(N)]
    print(*ans)


if __name__ == "__main__":
    resolve()

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] #x(根)の要素にｙ(根)のグループの要素数をプラスする(要素の値は負の数で表される)
        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 relf.roots()}

    def __str__(self): #ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
        return '\n'.join('{}:{}'.format(r,self.members(r)) for r in self.roots())

N,M,K=map(int,input().split())
uf=UnionFind(N)
friend=[0]*N
block=[0]*N

#友達関係
for i in range(M):
    a,b=map(int,input().split())
    uf.union(a-1,b-1) #a,bが所属するグループを併合
    friend[a-1]+=1
    friend[b-1]+=1

#ブロック関係
for i in range(K):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1): #同じグループだった場合
        block[c-1]+=1
        block[d-1]+=1

#(iを含むグラフの連結成分のサイズ)-(iと同一の連結成分に含まれている人のうち、iと友達関係にある人の数)-(iと同一の連結成分に含まれている人のうち、iとブロック関係にある人の数)-1
print(' '.join([str(uf.size(i)-friend[i]-block[i]-1) for i in range(N)]))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007
"""
#N,K,Mが入力
    n,k,m=LI() 
    #N
    #x1 y1
    #.  .
    #xn ynが入力
    N=I()
    p=LIR(N)
    print(n,k,m,p)
"""

############################## ユニオン木(union tree) ###################################
#uf=UnionFind(n)と使う
# print(uf.roots())
# print(uf.all_group_members())
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.par = [-1 for i in range(self.n+1)]
        self.rank = [0 for i in range(self.n+1)]#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。
    
    # 検索
    def find(self, x):
        # if self.par[x] == 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.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(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+1) if self.find(i) == root]

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

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

    #グループの数を返す
    def group_count(self):
        return len(self.roots())

    #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {int(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 resolve():
    n,m,k=LI()
    A=LIR(m)
    C=LIR(k)

    uf=UnionFind(n-1)
    # ub=UnionFind(n-1)
    dame=[[] for i in range(n)]
    for i in range(m):
        a=A[i][0]-1
        b=A[i][1]-1
        dame[a].append(b)
        dame[b].append(a)
        uf.union(a,b)

    for i in range(k):
        c=C[i][0]-1
        d=C[i][1]-1
        if uf.same(c,d)==True:
            dame[c].append(d)
            dame[d].append(c)
        # ub.union(c,d)

    # d=uf.all_group_members()
    # print(d)
    ans=[0]*n
    for i in range(n):
        ans[i]=str((uf.size(i)-1-len(dame[i])))
    L=' '.join(ans)

    print(L)


import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
a_m, b_m = [], []
c_k, d_k = [], []
def minus(x):
    return int(x)-1

friends_list = [[] for i in range(n)]
block_list = [[] for i in range(n)]
for i in range(m):
    a_m.append(0)
    b_m.append(0)
    a_m[i], b_m[i] = map(minus, input().split())
    friends_list[a_m[i]].append(b_m[i])
    friends_list[b_m[i]].append(a_m[i])
for i in range(k):
    c_k.append(0)
    d_k.append(0)
    c_k[i], d_k[i] = map(minus, input().split())
    block_list[c_k[i]].append(d_k[i])
    block_list[d_k[i]].append(c_k[i])

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents =[-1 for i in range(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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

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

def blocks_in_union(x):
    count = 0
    for block in block_list[x]:
        if uf.find(x) == uf.find(block):
            count += 1
    return count

uf = UnionFind(n)
for i in range(m):
    uf.unite(a_m[i], b_m[i])
for i in range(n):
    print(uf.size(i)-1-len(friends_list[i])-blocks_in_union(i), end=' ')

Submission status: Accepted

Solution code:
import queue

N,M,K=map(int,input().split())
friend=[[] for i in range(N)]
block=[[] for i in range(N)]
color=[-1]*N
c=0
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):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)

q=queue.Queue()
count=[0]*N

for i in range(N):
    if color[i]==-1:
        q.put(i)
        color[i]=c
        count[c]+=1
        while not q.empty():
            s=q.get()
            for t in friend[s]:
                if color[t]==-1:
                    color[t]=c
                    count[c]+=1
                    q.put(t)
        c+=1

for i in range(N):
    block_in_color=0
    for t in block[i]:
        if color[i]==color[t]:
            block_in_color+=1
    print(count[color[i]]-len(friend[i])-block_in_color-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())

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


n,m,k = map(int,input().split())
uf = UnionFind(n)
friends = [0]*n
blocks = [0]*n

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

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

print(' '.join([str(uf.size(i) - friends[i] - blocks[i] - 1) for i in range(n)]))

Submission status: Accepted

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

    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 False
        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)
friends = [0] * (N + 1)
blocks = [0] * (N + 1)
for _ in range(M):
    A, B = map(int, input().split())
    uf.union(A, B)
    friends[A] += 1
    friends[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        blocks[C] += 1
        blocks[D] += 1

print(" ".join([str(uf.size(i) - friends[i] - blocks[i] - 1) for i in range(1, N + 1)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
 
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    def getsize(self, x):
        return self.size[self.root(x)]
uf=UnionFind(n)
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    uf.merge(a-1,b-1)
    ans[a-1]-=1;ans[b-1]-=1
for i in range(k):
    c,d=map(int,input().split())
    if uf.issame(c-1,d-1):
        ans[c-1]-=1;ans[d-1]-=1
for i in range(n):
    ans[i]=uf.getsize(i)+ans[i]-1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.d = []
        for i 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
    #print(uf.size(i))
    ans -= len(dame[i])
    print(ans, end=" ")
print()

Submission status: Accepted

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

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

    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  = (int(i) for i in input().split())

#graph = np.zeros((N+1, N+1))
#graph2 = [[0] * (N+1) for i in range(N+1)]
uf = UnionFind(N)
fblist = [0] * (N+1)

for i in range(M):
    A, B =  (int(i) for i in input().split())
    uf.union(A, B)
    fblist[A] += 1
    fblist[B] += 1
 
for j in range(K):
    A, B =  (int(i) for i in input().split())
    if uf.same(A, B):
        fblist[A] += 1
        fblist[B] += 1

for i in range(1, N+1):
    print(uf.size(i) - fblist[i] - 1, end=" ")

print()