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:
# Union Find
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xの根とyを連結させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # xとyの親が同じ根か判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが連結している木の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
deg = [0 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    deg[a - 1] += 1
    deg[b - 1] += 1
    uf.union(a - 1, b - 1)

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

ans = []
for i in range(n):
    res = uf.size(i) - 1 - deg[i]
    for u in block[i]:
        if uf.same(i, u):
            res -= 1
    ans.append(res)

print(*ans)

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

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

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

for a, b in ab:
    uf.union(a, b) #RE

ans =[uf.get_size(i)-1 for i in range(N)]

for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
cut = [[] for i in range(n)]

par = [i for i in range(n)]
rank = [0]*n
size = [1]*n

def find(x, par):
    if x == par[x]:
        return x
    else:
        x = par[x]
        return find(x, par)
def unite(x, y, par, rank, size):
    x = find(x, par)
    y = find(y, par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a, b, par, rank, size)
    cut[a].append(b)
    cut[b].append(a)
for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if find(c, par) == find(d, par):
        cut[c].append(d)
        cut[d].append(c)
ans = []
for i in range(n):
    ans.append(size[find(i,par)]-len(cut[i])-1)
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.find(x) > self.find(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    def size(self, x):
        return -self.par[(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.par) 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())
a, b = [0] * m, [0] * m
c, d = [0] * k, [0] * k

direct =[[] for _ in range(n)]
uf = UnionFind(n)

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

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

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

print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_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.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  # print 表示用
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())


def get_result(data):
    N, M, K = data[0]
    A, B = [0] * M, [0] * M
    C, D = [0] * K, [0] * K
    direct = [[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
    uf = UnionFind(N)

    for i in range(M):
        A[i], B[i] = data[1+i]
        # 入力時に 0-index に合わせる
        A[i] -= 1
        B[i] -= 1
        direct[A[i]].append(B[i])
        direct[B[i]].append(A[i])
        uf.unite(A[i], B[i])

    for i in range(K):
        C[i], D[i] = data[1+M+i]
        # 入力時に 0-index に合わせる
        C[i] -= 1
        D[i] -= 1
        if uf.is_same(C[i], D[i]):
            direct[C[i]].append(D[i])
            direct[D[i]].append(C[i])

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.group_size(i) - len(direct[i]) - 1
    return ' '.join(list(map(str, ans)))


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
class Unionroot:
    def __init__(self, n=0):
        self.d = [-1]*n

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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

deg = [0] * 100005
to = [[] for i in range(100005)]

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

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

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

ret = []
for i in range(n):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    ret.append(ans)
print(' '.join([str(r) for r in ret]))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

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

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m,k = LI()
    ab = [LI_() for _ in range(m)]
    cd = [LI_() for _ in range(k)]
    e = collections.defaultdict(set)
    uf = UnionFind(n)
    for a,b in ab:
        e[a].add(b)
        e[b].add(a)
        uf.union(a,b)
    for c,d in cd:
        e[c].add(d)
        e[d].add(c)

    r = []
    for i in range(n):
        t = uf.find(i)
        s = -uf.table[t] - 1
        for j in e[i]:
            if uf.find(j) == t:
                s -= 1
        r.append(s)

    return JA(r, " ")


print(main())

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return True if self.find(x)==self.find(y) else False

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

    #出力用
    def __str__(self):
        return "\n".join("{}: {}".format(r,self.members(r)) for r in self.roots())
        #"\n"はただの改行コード
        #str(辞書)を改行しながら表示する
        #print(インスタンス)で__str__に飛ぶ
        #出力過程で、membersで全要素にfindをしてる→逐一経路圧縮されてる！


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


uf=UnionFind(n)


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

ans=[uf.size(i)-1 for i in range(n)] #自分を除く
for a,b in G:
    ans[a]-=1 ; ans[b]-=1
for a,b in B:
    if uf.same(a,b):
        ans[a]-=1 ; ans[b]-=1

print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# D - Friend Suggestions

from collections import deque

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

adj = {a: [] for a in range(1, n+1)}
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# 連結成分

connOf = {}
for a in range(1, n+1):
    if a in connOf:
        continue
    conn = set()
    queue = deque()
    queue.append(a)
    while len(queue) > 0:
        p = queue.popleft()
        if p not in conn:
            conn.add(p)
            connOf[p] = conn
            queue.extend(adj[p])

# (同じ連結成分中の)ブロック関係

block = {a: [] for a in range(1, n+1)}
for i in range(k):
    c, d = map(int, input().split())
    if c in connOf[d]:
        block[c].append(d)
        block[d].append(c)

# 友達候補 = 同じ連結成分 - 自分 - 友達関係 - ブロック関係

nCandidate = [len(connOf[a]) - 1 - len(adj[a]) - len(block[a])
  for a in range(1, n+1)]
print(' '.join(map(str, nCandidate)))

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

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


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


friend_checker = UnionFind(N)
direct_friends = [0 for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    friend_checker.union(A - 1, B - 1)
    direct_friends[A - 1] += 1
    direct_friends[B - 1] += 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)

for i in range(N):
    ans = friend_checker.size(i) - direct_friends[i] - 1
    for l in block[i]:
        if friend_checker.same(i, l):
            ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
import math
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

N,M,K = nm()

# parent
# if negative, it means the node is root and the value is the size of the group. 
par=[-1] * N  

# return the root node number of the group which the node x belong to  
def find(x):  
  if par[x]<0:  # this means that node x is a root node of the group
    return x    
  else:
    par[x]=find(par[x])  # the parent nodes is expected to have root node number info.
        # if the parent node were not root node, par[x] will be update to be a root node.
        # For the next search par[x] will be the root node. 
    return par[x]

# Unite the group which node x belongs to and the group which node y belongs to 
def unite(x,y):
  x=find(x)  # x will be a root node of the original x node 
  y=find(y)  # y will be a root node of the original y node
  if x==y:   # x and y belong to the same group already, do nothing and just return False 
    return False
  else:  
    if par[x]>par[y]: # Note this is size comparison
      # Size of the group x is smaller than that of the group y, then swap x and y  
      # Note, we are using negative number 
      x,y=y,x
    par[x]+=par[y]  # the size of the group x is increased by the size of the group y 
    par[y]=x  # now the parent of the node y is set to node x.
       # At this moment, parent of other nodes which belonged to the old group y is 
       # stil node Y. However, after find() for those nodes will be update the info  
    return True

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

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

links=[0]*N   # set to all -1. Nubmer of friend and block + 1 
F = [0]* N 
for _ in range(M):
    A,B = nm()
    unite(A-1,B-1)
    links[A-1] +=1 
    links[B-1] +=1

for _ in range(K):
    C,D = nm()
    if same(C-1,D-1):
        links[C-1]+=1
        links[D-1]+=1

for i in range(N):
    F[i] = size(i) - 1 - links[i]
print(*F)

Submission status: Accepted

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
            union_count[root_s] += union_count[root_t]
        elif rank[s] > rank[t]:
            root[root_t] = root_s
            union_count[root_s] += union_count[root_t]
        else:
            root[root_s] = root_t
            union_count[root_t] += union_count[root_s]

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m, k = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
union_count = [1 for _ in range(n)]
friend_count = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
    friend_count[a - 1] += 1
    friend_count[b - 1] += 1
ans = [-1] * n
for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        ans[c - 1] -= 1
        ans[d - 1] -= 1
for i in range(n):
    r = get_root(i)
    ans[i] += union_count[r] - friend_count[i]
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


# UnionFind

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x): # O(α(n))
        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): # O(α(n))
        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): #O(1)
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    adjacency_list = [[] for _ in range(N+1)]
    uf = UnionFind(N+1)
    for i in range(M):
        adjacency_list[A[i]].append(B[i])
        adjacency_list[B[i]].append(A[i])
        uf.union(A[i],B[i])
    
    answer = []
    block_count = [0]*(N+1) # i と同じグループにいてかつブロックしてる人数
    for k in range(K):
        if uf.same(C[k],D[k]):
            block_count[C[k]] += 1
            block_count[D[k]] += 1
        

    for i in range(1,N+1):
        size = uf.size(i) # iがいるグループのサイズ
        answer.append(size-len(adjacency_list[i])-block_count[i]-1)
    print(*answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(1000000)
    n, m, k = map(int, input().split())
    friends = [set() for i in range(n)]
    blocks = [set() for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)
        unite(a - 1, b - 1, parents)
    for i in range(k):
        c, d = map(int, input().split())
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)
    groups = [set() for i in range(n)]
    for i in range(n):
        p = find(i, parents)
        groups[p].add(i)
    res = []
    for i in range(n):
        p = find(i, parents)
        res.append(len(groups[p]) - len(friends[i]) - len(groups[p] & blocks[i]) - 1)
    print(" ".join([str(x) for x in res]))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar 13 19:30:22 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import defaultdict

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

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self._size[y] += self._size[x]
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]

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

n, m, k = na()
ab = nan(m)
cd = nan(k)

friend = defaultdict(int)
uf = UnionFind(n)

for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    uf.unite(a, b)
    friend[a] += 1
    friend[b] += 1

block = defaultdict(list)
for i in range(k):
    c, d = cd[i]
    c -= 1
    d -= 1
    block[c].append(d)
    block[d].append(c)
ans = []
for i in range(n):
    bf = 0
    for j in block[i]:
        if uf.same(i, j):
            bf += 1
    ans.append(uf.size(i) - friend[i] - bf - 1)

print(*ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

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

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

#import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  #q = queue.Queue()
  #q.put(i)
  stack = [i]
  #while not q.empty():
  while len(stack)>0:
    #print('v:',visited)
    #p = q.get()
    p = stack.pop()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        #q.put(f)
        stack.append(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)

Submission status: Accepted

Solution code:
#木の根を得る
def root(x):
    while par[x] >= 0:
        x = par[x]
    return x

#木の併合
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        if rx > ry:
            rx,ry = ry,rx
        par[rx] += par[ry]
        par[ry] = rx

#2つのデータx,yが属する木が同じならtrueを返す
def same(x,y):
    rx = root(x)
    ry = root(y)
    return rx == ry

#属する木のサイズ
def size(x):
    return -par[root(x)]

#ABC157D
N,M,K = map(int,input().split())
par = [-1]*N
g = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    unite(A,B)
    g[A].append(B)
    g[B].append(A)

for i in range(K):
    C,D = map(int,input().split())
    C,D = C-1,D-1
    if same(C,D):
        g[C].append(D)
        g[D].append(C)

for i in range(N):
    print(size(i)-len(g[i])-1,end=' ')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

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

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

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,M,K=map(int,readline().split())
    #UnionFind
    t=UnionFind(N)
    fb=[set() for _ in range(N)]
    for _ in range(M):
        a,b=map(int,readline().split())
        t.union(a-1,b-1)
        if b-1 not in fb[a-1]:
            fb[a-1].add(b-1)
        if a-1 not in fb[b-1]:
            fb[b-1].add(a-1)
    
    for _ in range(K):
        c,d=map(int,readline().split())
        if t.are_same(c-1,d-1):
            if d-1 not in fb[c-1]:
                fb[c-1].add(d-1)
            if c-1 not in fb[d-1]:
                fb[d-1].add(c-1)

    res=[0]*N
    for i in range(N):
        res[i]=t.element_count(i)-1-len(fb[i])

    print(*res)

if __name__=="__main__":
    main()