Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

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

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

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

    friends = defaultdict(lambda : 1)
    friendsGroup = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friendsGroup.union(a, b)
        friends[a] += 1
        friends[b] += 1

    blocks = defaultdict(int)
    for _ in range(K):
        c, d = map(int, input().split())
        if friendsGroup.same(c, d):
            blocks[c] += 1
            blocks[d] += 1

    ans = [friendsGroup.size(i) - friends[i] - blocks[i] for i in range(1, N+1)]
    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, k = input().strip().split()
n, m, k = int(n), int(m), int(k)
friends = [0] + [[] for _ in range(n)]
blocks = [0] + [[] for _ in range(n)]

for _ in range(m):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    friends[p1].append(p2)
    friends[p2].append(p1)
for _ in range(k):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    blocks[p1].append(p2)
    blocks[p2].append(p1)

connected_num = 0
def dfs(graph, current, seen, connected_id):
    global connected_num
    seen[current] = connected_id
    connected_num += 1

    children = graph[current]
    for c in children:
        if seen[c] != -1:
            continue
        dfs(graph, c, seen, connected_id)

seen = [-1] * (n + 1)
connected_id = 0
connected = []
for i in range(1, n + 1):
    if seen[i] != -1:
        continue
    dfs(friends, i, seen, connected_id)
    connected.append(connected_num)
    connected_num = 0
    connected_id += 1

ans = []
for i in range(1, n + 1):
    i_connected_id = seen[i]
    exclude = 0
    for f in friends[i]:
        f_connected_id = seen[f]
        if i_connected_id == f_connected_id:
            exclude += 1
    for b in blocks[i]:
        b_connected_id = seen[b]
        if i_connected_id == b_connected_id:
            exclude += 1
    ans.append(str(connected[i_connected_id] - exclude - 1))

print(' '.join(ans))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, input().split()) #整数-1map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime



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 False

        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 = imn()
uf = UnionFind(N)
friends_cnt = [0 for _ in range(N)]
blocks = [[] for _ in range(N)]
for i in range(M):
    a, b = imnn()
    friends_cnt[a] += 1
    friends_cnt[b] += 1
    uf.union(a, b)
for i in range(K):
    a, b = imnn()
    blocks[a].append(b)
    blocks[b].append(a)

ans = []
for i in range(N):
    num = uf.size(i)-1-friends_cnt[i]
    for b in blocks[i]:
        if uf.same(i, b): num -= 1
    ans.append(str(num))
print(' '.join(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 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)
n_friend = [0 for i in range(n)]

for i in range(m):
    ai, bi = map(int, input().split())
    uf.union(ai-1, bi-1)
    n_friend[ai-1] += 1
    n_friend[bi-1] += 1
for i in range(n):
    uf.find(i)

block = [[] for i in range(n)]
for i in range(k):
    ci, di = map(int, input().split())
    block[ci-1].append(di-1)
    block[di-1].append(ci-1)

lst = []
for i in range(n):
    num = uf.size(i) - n_friend[i] - 1
    for j in block[i]:
        if uf.find(i) == uf.find(j):
            num -= 1
    lst.append(num)

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

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

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

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] < self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp
    
    def print(self):
        ret = {}
        for i in range(len(self.table)):
            p = self.find(i)
            if p not in ret:
                ret[p] = {i}
            else:
                ret[p].add(i)
        print(ret)

    def size(self, x):
        p = self.find(x)
        return -self.table[p]

n, m, k = map(int, input().split())
u = Unionfind(n)
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    u.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
block = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

answer = []
for i in range(n):
    ans = u.size(i) - 1
    for e in block[i]:
        if u.same(i, e):
            ans -= 1
    answer.append(ans - len(friend[i]))
print(*answer)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
friends = [set() for _ in range(n)]
blocked = [set() for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)
    
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blocked[c].add(d)
    blocked[d].add(c)

checked = set()
ans = [0]*n
for i in range(n):
    if i in checked:
        continue
        
    fgroup = set()
    
    stack = list(friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue
        checked.add(f)
        fgroup.add(f)
        stack.extend(friends[f])
        
    for f in fgroup:
        ans[f] = len(fgroup) - 1 -len(fgroup&(friends[f]|blocked[f]))
    
print(" ".join(map(str,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 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 get(self):
      return [self.members(r) for r in self.roots()][1:]

N,M,K = map(int,input().split())
f_arr = [0 for _ in range(N+1)]
uf = UnionFind(N+1)
for i in range(M):
  a,b = map(int,input().split())
  uf.union(a,b)
  f_arr[a] += 1
  f_arr[b] += 1
for j in range(K):
  a,b = map(int,input().split())
  if uf.same(a,b):
    f_arr[a] += 1
    f_arr[b] += 1

arr = []
for k in range(1,N+1):
  ans = uf.size(k)-f_arr[k] -1
  arr.append(ans)
print(*arr)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n+1
        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)

    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 = list(map(int, input().split()))
friend = [0]*(n+1)
tree = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    tree.union(a, b)

ans = [0]*(n+1)
for i in range(1, n+1):
    ans[i] = tree.size(i) - friend[i] - 1

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


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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

class UnionFind:
    def __init__(self, n):
        # 負 : 根である．絶対値はランク
        # 正 : 根じゃない．値は親の番号
        self.root_table = [-1] * n
        # 自分の下に何個あるか(自分含む)
        self.count_table =  [1] * n
 
    def get_root(self, x):
        if self.root_table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.root_table[x] = self.get_root(self.root_table[x])
            return self.root_table[x]
 
    def find(self, x, y):
        return self.get_root(x) == self.get_root(y)
 
    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return

        # ランクの取得
        d1 = self.root_table[r1]
        d2 = self.root_table[r2]
        # 値が小さいほど深い木である(絶対値が大きい)
        if d1 <= d2:
            self.root_table[r2] = r1
            self.count_table[r1] += self.count_table[r2]
            # 深さが同じ時はランクが増える
            if d1 == d2:
                self.root_table[r1] -= 1
        else:
            self.root_table[r1] = r2
            self.count_table[r2] += self.count_table[r1]
        
    def count(self, x):
        return self.count_table[self.get_root(x)]


N, M, K = MI()
AB = LRI(M)
CD = LRI(K)

uf = UnionFind(N + 1)
friend = [0] * (N + 1)

for ab in AB:
    a, b = ab

    friend[a] -= 1
    friend[b] -= 1

    uf.union(a, b)

for cd in CD:
    c, d = cd

    if uf.find(c, d):
        friend[c] -= 1
        friend[d] -= 1

for i in range(1, N + 1):
    friend[i] += (uf.count(i) - 1)

print(*friend[1:])

Submission status: Accepted

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

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

Blocked = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].add(d)
    Blocked[d].add(c)

# process
# 友人グループを作成
checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

# output
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N,M,K = map(int,input().split())
 
par = [i for i in range(N+1)]
 
# 木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]
 
# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)
 
# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y
 
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]
 
for a,b in AB:
    unite(a,b)
 
for i in range(N+1):
    root(i)
 
member = [0 for i in range(N+1)]
 
for p in par:
    member[p] += 1
 
ans = [member[par[i]]-1 for i in range(N+1)]
 
for a,b in AB:
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for c,d in CD:
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

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

# 木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

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

for i in range(M):
    a,b = AB[i]
    unite(a,b)

member = [0 for i in range(N+1)]

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

ans = [member[par[i]]-1 for i in range(N+1)]

for i in range(M):
    a,b = AB[i]
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1

for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque
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)]

f1 = [set() for _ in range(0, n+1)]
b1 = [set() for _ in range(0, n+1)]
fb1 = [set() for _ in range(0, n+1)]
ans = [0]*(n+1)

for x,y in ab:
    f1[x].add(y)
    f1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

for x,y in cd:
    b1[x].add(y)
    b1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

stack = deque()
visited = [0]*(n+1)
links = []

for i in range(1, n+1):
    if visited[i]: continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n1 = stack.pop()
        for j in f1[n1]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    links.append(link)

for i in links:
    leni = len(i)
    for j in i:
        ans[j] = leni - len(i & fb1[j]) - 1

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
N, M, K = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
C = [0]*K
D = [0]*K
for i in range(K):
    C[i], D[i] = map(int,input().split())

friend = {i: set([]) for i in range(1, N+1)}
brock = {i: set([]) for i in range(1, N+1)}
for i in range(M):
    friend[A[i]].add(B[i])
    friend[B[i]].add(A[i])
for i in range(K):
    brock[C[i]].add(D[i])
    brock[D[i]].add(C[i])

labels = [0] * (N+1)


def mark(n, label):
    if labels[n] != 0:
        return -1
    else:
        q = deque()
        q.append(n)
        labels[n] = label
        while q != deque():
            node = q.pop()
            labels[node] = label
            for i in friend[node]:
                if labels[i] == 0:
                    q.append(i)
        return label


label = 1
for n in range(1, N + 1):
    if mark(n, label) != -1:
        label += 1

group_size = Counter(labels)

res = [0] * N
for n in range(1, N + 1):
    tmp = 0
    for b in brock[n]:
        if labels[n] == labels[b]:
            tmp += 1
    res[n - 1] = group_size[labels[n]] - 1 - len(friend[n]) - tmp

print(*res)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

    def all_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)
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)
    uf.union(a,b)

es_block_in_union = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    if uf.is_same(c,d):
        es_block_in_union[c].append(d)
        es_block_in_union[d].append(c)


ans = [0]*n
for i in range(n):
    ans[i] =  uf.size(i) - len(es_block_in_union[i])  - len(es1[i]) -1

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
class UnionFind():
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n
        
    def find(self, a):
        if self.parents[a] < 0:
            return a
        else:
            self.parents[a]=self.find(self.parents[a])
            return self.parents[a]
        
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        else:
            if self.parents[x]<self.parents[y]:
                x,y = y,x
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def same(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False
    
N,M,K = map(int,input().split())
uf = UnionFind(N)
friend = [list(map(int,input().split())) for i in range(M)]
block = [list(map(int,input().split())) for i in range(K)]
ff = [[] for i in range(N)]
bb = [[] for i in range(N)]
ans = []
for i in range(M):
    uf.union(friend[i][0]-1,friend[i][1]-1)
    ff[friend[i][0]-1].append(friend[i][1]-1)
    ff[friend[i][1]-1].append(friend[i][0]-1)
for i in range(K):
    bb[block[i][0]-1].append(block[i][1]-1)
    bb[block[i][1]-1].append(block[i][0]-1)
for i in range(N):
    ans.append(uf.size(i)-1-len(ff[i]))
    for j in bb[i]:
        if uf.same(j,i)==True:
            ans[i] -= 1
answer=[str(ans[i]) for i in range(len(ans))]
print(" ".join(answer))

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

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

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
class UnionFind():
    def __init__(self, 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 resolve():
    N, M, K = lr()
    uf = UnionFind(N)
    fr = [0]*N
    for i in range(M):
        a, b = lr()
        uf.union(a-1, b-1)
        fr[a-1] += 1
        fr[b-1] += 1
    ans = [uf.size(x) - fr[x] - 1 for x in range(N)]
    for i in range(K):
        c, d = lr()
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1
    print(*ans, sep=' ')
resolve()

Submission status: Accepted

Solution code:
def find(x): #xの根を求める
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y): #xとyの属する集合の併合
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def same(x,y): #xとyが同じ集合に属するかの判定
    return find(x) == find(y)

def size(x): #xが属する集合の個数
    return -par[find(x)]

N,M,K = map(int, input().split())
par = [-1]*(N+1)
fri = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
    unite(a,b)

bro = [[] for i in range(N+1)]
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

ans = [0]*N
for i in range(1,N+1):
    ans[i-1] = size(i)-1
    for f in fri[i]:
        if same(f,i): ans[i-1] -= 1
    for b in bro[i]:
        if same(b,i): ans[i-1] -= 1

# print(par)
ans = list(map(str,ans))
print(" ".join(ans))

Submission status: Accepted

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

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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(uf.size(i) - len(block_list[i]))
print(*ans)