Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    union_find = UnionFind(N)
    friends = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)
        union_find.union(a, b)
    blacks = [[] for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blacks[c].append(d)
        blacks[d].append(c)
    ans = []
    for i in range(N):
        a = union_find.size(i) - len(friends[i])
        for black in blacks[i]:
            if union_find.same(i, black):
                a -= 1
        ans.append(a-1)
    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

friends = UnionFind(N)
for a, b in AB:
    friends.union(a, b)

ans = [0] * N
for i in range(N):
    ans[i] = friends.sizeOfSameRoot(i) - 1
for a, b in AB:
    ans[a] -= 1
    ans[b] -= 1
for c, d in CD:
    if friends.isSameRoot(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
n,m,k = [int(i) for i in input().split()]
ans = [-1]*n

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

par = [-1]*n
g = [[] * n for i in range(n)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  ans[a-1] -= 1
  ans[b-1] -= 1
  
def same(x,y):
    return find(x) == find(y)
for i in range(k):
  u, v = map(int, input().split())
  if same(u-1,v-1):
    ans[u-1] -= 1
    ans[v-1] -= 1
  
for i in range(n):
  ans[i] += size(i)
  
print(*ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    AB = [[int(i)-1 for i in input().split()] for j in range(M)]
    CD = [[int(i)-1 for i in input().split()] for j in range(K)]

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

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    friends = [[] for _ in range(N)]
    blocks = [[] for _ in range(N)]
    for a, b in AB:
        friends[a].append(b)
        friends[b].append(a)
        unite(a, b)
    for c, d in CD:
        if is_same_group(c, d):
            blocks[c].append(d)
            blocks[d].append(c)
    for i in range(N):
        ans = size(i) - len(friends[i]) - len(blocks[i]) - 1
        print(ans, end=" " if i != N-1 else "\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


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


def main():
    n, m, k = map(int, input().split())
    fg = [[] for _ in range(n)]
    uf = UnionFind(n)
    bg = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fg[a].append(b)
        fg[b].append(a)
        uf.union(a, b)
    for _ in range(k):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bg[c].append(d)
        bg[d].append(c)
    ans = [0] * n
    for i in range(n):
        ans[i] = uf.size(i)-1
        for f in fg[i]:
            if uf.same(f, i):
                ans[i] -= 1
        for b in bg[i]:
            if uf.same(b, i):
                ans[i] -= 1
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]


n, m, k = map(int, input().split())
b = [list(map(int, input().split())) for i in range(m)]
c = [list(map(int, input().split())) for i in range(k)]

uf = UnionFind(n)
b_graph = [[] for i in range(n)]
for u, v in b:
    u -= 1
    v -= 1
    uf.merge(u, v)
    b_graph[u].append(v)
    b_graph[v].append(u)
    
c_graph = [[] for i in range(n)]
for u, v in c:
    u -= 1
    v -= 1
    c_graph[u].append(v)
    c_graph[v].append(u)

ans = []
for i in range(n):
    res = uf.get_size(i) - 1
    res -= len(b_graph[i])
    for v in c_graph[i]:
        if uf.is_same(i, v):
            res -= 1
    ans.append(res)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

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


def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    friend = [[] for _ in range(n)]
    answer = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.is_same(c, d):
            answer[c] -= 1
            answer[d] -= 1
    for i in range(n):
        answer[i] += uf.get_size(i) - len(friend[i])
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
ab = [list(map(int, readline().split())) for _ in range(m)]
cd = [list(map(int, readline().split())) for _ in range(k)]
uf = UnionFind(n + 1)
cnt = [-1] * n
for a, b in ab:
    uf.union(a, b)
for i in range(n):
    cnt[i] += uf.size(i + 1)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


uf = UnionFind(N)
for i in range(N):
    for j in friends[i]:
        uf.union(i, j)

ans = []
for i in range(N):
    res = uf.size(i) - len(friends[i]) - 1
    for b in blocked[i]:
        if uf.same(i, b):
            res -= 1
    ans.append(res)
print(*ans)

Submission status: Accepted

Solution code:
from itertools import chain
 
n,m,k = map(int,input().split())
 
bff = [list(map(int,input().split())) for i in range(m)]
 
blk = [list(map(int,input().split())) for i in range(k)]
 
 
rank = [0] * (n+1)
par = [i for i in range(n+1)]
demi = [1] * (n+1)
 
 
for i,j in bff:
    x = par[i]
    y = par[j]
    while x != par[x]:
        x = par[x]
    while y != par[y]:
        y = par[y]
    if(x == y):
        continue
    
    if rank[x] < rank[y]:
        par[x] = y
        demi[y] += demi[x]
        
    else:
        par[y] = x
        demi[x] += demi[y]
        
        if rank[x] == rank[y]:
             rank[x] += 1
 
 
for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    par[i+1] = x
 
 
for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    demi[i+1] = demi[x]
 
 
 
a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))
 
fqua = [0] * n
bqua = [0] * n
 
for i,j in bff:
    if(par[i] == par[j]):
        fqua[i-1] += 1
        fqua[j-1] += 1
 
for i,j in blk:
    if(par[i] == par[j]):
        bqua[i-1] += 1
        bqua[j-1] += 1
 
for i in range(n):
    print(demi[i+1] - fqua[i] - bqua[i] - 1 ,end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)

groups = {}
for i in range(N):
    if i in groups:
        continue
    group = {i}
    stack = [(i, None)]
    while stack:
        j, parent_id = stack.pop()
        group.add(j)
        groups[j] = group
        for k in friends[j]:
            if k != parent_id and k not in groups:
                stack.append((k, j))

ans = []
for i in range(N):
    g = groups[i]
    res = len(g) - len(friends[i]) - 1
    for b in blocked[i]:
        if groups[b] is g:
            res -= 1
    ans.append(res)
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)


class UF:
    def __init__(self, node_id):
        self.node_id = node_id
        self._root = self
        self._size = 1

    @property
    def root(self):
        p = self._root
        while p is not p._root:
            p = p._root
        q = self
        while q._root is not p:
            r = q._root
            q._root = p
            q = r
        return p

    @property
    def size(self):
        return self.root._size

    def merge(self, other):
        if self.root.node_id == other.root.node_id:
            return self.root
        elif self.root.node_id < other.root.node_id:
            self.root._size += other.root._size
            other._root = self.root
            return self.root
        else:
            other.root._size += self.root._size
            self._root = other.root
            return other.root


sets = [UF(i) for i in range(N)]
visited = set()
for i in range(N):
    if i in visited:
        continue
    r = sets[i]
    stack = [(i, None)]
    while stack:
        j, parent_id = stack.pop()
        if j in visited:
            continue
        visited.add(j)
        for k in friends[j]:
            if k != parent_id:
                r = r.merge(sets[k])
                if k not in visited:
                    stack.append((k, j))

ans = []
for i in range(N):
    res = sets[i].size - len(friends[i]) - 1
    root_id = sets[i].root.node_id
    for b in blocked[i]:
        if sets[b].root.node_id == root_id:
            res -= 1
    ans.append(res)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
import time
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_relations = [[] for _ in range(N+1)]
block_relations = [[] for _ in range(N+1)]

num_connected_friends = [0] * (N+1)
num_connected_blocks = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    friend_relations[A].append(B)
    friend_relations[B].append(A)

for _ in range(K):
    C, D = map(int, input().split())
    block_relations[C].append(D)
    block_relations[D].append(C)

if DEBUG:
    print("friend_relations:")
    for i, row in enumerate(friend_relations):
        print("node: {}, relation: {}".format(i, row))
    print("block_matrix:")
    for i, row in enumerate(block_relations):
        print("node: {}, relation: {}".format(i, row))

count = 0
labels = [-1] * (N+1)
graph_sizes = []
total_iteration = 0
for n in range(1, N+1):
    if DEBUG:
        print("root_node: {}, count: {}".format(n, count))
    if labels[n] == -1:
        queue = deque([n])
        labels[n] = count
        size = 0
        while queue:
            if DEBUG:
                print("queue:{}".format(queue))
            node = queue.popleft()
            size += 1
            if DEBUG:
                print("node:{}".format(node))
            for next_node in friend_relations[node]:
                total_iteration += 1
                if labels[next_node] == -1:
                    labels[next_node] = count
                    queue.append(next_node)
            if DEBUG:
                print("labels: {}".format(labels))
            # time.sleep(0.2)
        count += 1
        graph_sizes.append(size)
if DEBUG:
    print("total_iteration: {}".format(total_iteration))
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

friend_candidate = [0] * (N+1)
for n in range(1, N+1):
    num_block = sum([1 for i in block_relations[n] if labels[n] == labels[i]])
    num_frined = len(friend_relations[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    friend_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1

print(*friend_candidate[1:])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
#node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]

N = list(map(int, input().split()))
parents = [-1] * N[0]
def find(x):
  if parents[x] < 0:
    return x
  else:
    parents[x] = find(parents[x])
    return parents[x]

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

  if x == y: return False
  if parents[x] > parents[y]:
    x, y = y, x
  parents[x] += parents[y]
  parents[y] = x
        
def issame(x, y):
  return find(x) == find(y)
  
def size(x):
  return -parents[find(x)]
  

results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
#print(node_members, results)

print(" ".join([str(size(i) - results[i] - 1) for i in range(N[0])]))

Submission status: Accepted

Solution code:
from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    trace.add(i)
    searched[i] = 1
    while d:
        temp = d.popleft()
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
                trace.add(x)
                searched[x] = 1
    chain = len(trace)
    for j in trace:
        ans[j] = chain - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 ** 30)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))

Submission status: Accepted

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

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

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
pot = [uf.size(i)-1 for i in range(N)]
for i in range(M):
    A,B = AB[i][0],AB[i][1]
    if uf.find(A-1) == uf.find(B-1):
        pot[A-1] -= 1
        pot[B-1] -= 1
for i in range(K):
    C,D = CD[i][0],CD[i][1]
    if uf.find(C-1) == uf.find(D-1):
        pot[C-1] -= 1
        pot[D-1] -= 1
print(*pot)

Submission status: Accepted

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

    def find(self, x):
        if self.par[x] == x:
            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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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


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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

uf = UnionFind(n)

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

    uf.union(a-1, b-1)

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

candidate = [0] * n

for i in range(n):
    candidate[i] = uf.get_size(i) - len(friend[i]) - 1
    for j in block[i]:
        if uf.is_same(i, j):
            candidate[i] -= 1

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