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


uf = UnionFind(N)

edge1 = []
edge2 = []

for _ in range(M):
    a, b = map(int, input().split())
    edge1.append((a - 1, b - 1))

for _ in range(K):
    a, b = map(int, input().split())
    edge2.append((a - 1, b - 1))

for a, b in edge1:
    uf.union(a, b)

res = [uf.size(i) - 1 for i in range(0, N)]

for a, b in edge1:
    res[a] -= 1
    res[b] -= 1

for a, b in edge2:
    if uf.same(a, b):
        res[a] -= 1
        res[b] -= 1

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

Submission status: Accepted

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

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

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

fre = [set() for i in range(N)]

for i in range(M):
  a, b = map(int, input().split())
  fre[a-1].add(b-1)
  fre[b-1].add(a-1)
  uf.unite(a-1, b-1)

ble = [tuple(map(int, input().split())) for i in range(K)]

ans = [0] * N
t = {}
for n in range(N):
  t[uf.root(n)] = t.get(uf.root(n), 0) + 1

for n in range(N):
  ans[n] = t[uf.root(n)] - len(fre[n]) - 1

for a, b in ble:
  if uf.same(a-1, b-1):
    ans[a-1] -= 1
    ans[b-1] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
n, m, k = [int(i) for i in sys.stdin.readline().split()]

par = list(range(n))
ns = [1 for i in range(n)]

def find(x):
    ls = []
    while x != par[x]:
        ls.append(x)
        x = par[x]
    for l in ls:
        par[l] = x
    return x

def unite(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y
        ns[y] += ns[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

ls = [0 for i in range(n)]
friends = [0 for i in range(n-1)]

for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls[a] -= 1
    ls[b] -= 1
    unite(a, b)

for i in range(n):
    root = find(i)
    ls[i] += ns[root]


for i in range(k):
    c, d = [int(i) for i in sys.stdin.readline().split()]
    c -= 1
    d -= 1
    if is_same(c, d):
        ls[c] -= 1
        ls[d] -= 1

print(" ".join([str(i - 1) for i in ls]))

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

def main():
    N, M, K = map(int, input().split())
    fd = defaultdict(list)
    uf = UnionFind(N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        if a in fd:
            fd[a].append(b)
        else:
            fd[a] = [b]
        if b in fd:
            fd[b].append(a)
        else:
            fd[b] = [a]
        uf.union(a,b)
    for _ in range(K):
        c, d = map(int, input().split())
        if uf.same(c, d):
            fd[c].append(d)
            fd[d].append(c)
    r = []
    for i in range(1, N+1):
        r.append(uf.size(i)-len(fd[i])-1)
    print(' '.join(str(i) for i in r))
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m, k = LI()
    ab = LIR_(m)
    cd = LIR_(k)
    par = [i for i in range(n)]
    size = [1] * n
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

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

    lis = [1] * n
    for a, b in ab:
        unite(a, b)
        lis[a] += 1
        lis[b] += 1
    for c, d in cd:
        if root(c) == root(d):
            lis[c] += 1
            lis[d] += 1
    for i in range(n):
        print(size[root(i)] - lis[i], end=" ")
    print()
    return


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

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  #k  = [i,j].min
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n,m,k = inm()
ufinit(n+1)
friend = [{} for i in range(n+1)]
for i in range(m):
    a,b = inm()
    friend[a][b] = 1
    friend[b][a] = 1
    ufconn(a,b)
blk = [{} for i in range(n+1)]
for i in range(k):
    a,b = inm()
    blk[a][b] = 1
    blk[b][a] = 1
gr = {}
for i in range(1,n+1):
    r = ufroot(i)
    if r in gr:
        gr[r] += 1
    else:
        gr[r] = 1
for i in range(1,n+1):
    r = ufroot(i)
    x = gr[r]-1
    for f in friend[i]:
        if ufroot(f)==r:
            x -= 1
    for f in blk[i]:
        if ufroot(f)==r:
            x -= 1
    printn(str(x)+' ')
print("")

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a
# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx # 根をbxに統一

N, M, K = lr()
AB = [lr() for _ in range(M)]
friends = [[] for _ in range(N+1)]
block = [set() for _ in range(N+1)]
for a, b in AB:
    friends[a].append(b)
    friends[b].append(a)

for _ in range(K):
    c, d = lr()
    block[c].add(d)
    block[d].add(c)

V = [i for i in range(N+1)] # 1-indexed
for a, b in AB:
    if find(V, a) != find(V, b):
        union(V, a, b)

for i in range(1, N+1):
    V[i] = find(V, i)

for i in range(1, N+1):
    rmv = set()
    for x in block[i]:
        if V[i] != V[x]:
            rmv.add(x)
    block[i] -= rmv

counter = Counter(V)

answer = [None] * (N+1)
for i in range(1, N+1):
    num = counter[V[i]]
    answer[i] = num - len(friends[i]) - len(block[i]) - 1

print(*answer[1:])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)] #親要素のノード番号を格納
        self.rank=[0]*n #木の高さを格納
        self.size=[1]*n #size[i]:iを根とするグループのサイズ
    def find(self,x): #根を検索
        if self.par[x]==x: #par[x]==xの時そのノードは根
            return x
        else:
            self.par[x]=self.find(self.par[x]) #親を書き換える
            return self.par[x]
    def union(self,x,y):
        px=self.find(x)
        py=self.find(y)
        if px!=py:
            if self.rank[px]==self.rank[py]: #木の高さが同じなら親とする方を1増やす
                self.rank[px]+=1
            elif self.rank[px]<self.rank[py]:
                px,py=py,px #木の高さが高い方をpxとする
            self.par[py]=px #木の高さが高い方を親とする
            self.size[px]+=self.size[py]
    def same_check(self,x,y): #同じ木に属するか判定
        return self.find(x)==self.find(y)
    
def main():
    n,m,k=map(int,input().split())
    uf=UnionFind(n)
    F_edges=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1
        uf.union(a,b)
        F_edges[a].append(b)
        F_edges[b].append(a)
    B=[0]*n
    for _ in range(k):
        a,b=map(int,input().split())
        a-=1; b-=1
        if uf.same_check(a,b):
            B[a]+=1
            B[b]+=1
    Ans=[]
    for i in range(n):
        Ans.append(uf.size[uf.find(i)]-1-len(F_edges[i])-B[i])
    print(*Ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

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

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

n, m, k = map(int, input().split())
U = UnionFind(n)
may_friend = [-1 for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    U.union(a, b)
    may_friend[a] += -1
    may_friend[b] += -1
for i in range(k):
    c, d = map(int, input().split())
    if U.check(c, d):
        may_friend[c] += -1
        may_friend[d] += -1

ans = [max(0, may_friend[i] + U.size(i)) for i in range(1, n + 1)]
print(*ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(500000)

# class UnionFind:

#     def __init__(self, n):
#         self.n = n
#         self.parent = [0] * (n+3)
#         self.num = [1] * (n+3)
#         self.diff_weight = [0] * (n+3)
#         for i in range(n):
#             self.parent[i] = i
    
#     def root(self, x):
#         if x == self.parent[x]:
#             return x
#         else:
#             r = self.root(self.parent[x])
#             self.diff_weight[r] += self.diff_weight[self.parent[x]]
#             self.parent[x] = r
#             return r
    
#     def unite(self, a, b, w = 0):
#         w += self.weight(a) - self.weight(b)
#         a = self.root(a)
#         b = self.root(b)
#         if a == b:
#             return
#         self.parent[b] = a
#         sum_v = self.num[a] + self.num[b]
#         self.num[a] = sum_v
#         self.num[b] = sum_v
#         self.diff_weight[b] = w
        
#     def same(self, a, b):
#         return (self.root(a) == self.root(b))
    
#     def sz(self, x):
#         return self.num[self.root(x)]
    
#     def weight(self, x):
#         self.root(x)
#         return self.diff_weight[x]

#     def diff(self, a, b):
#         return self.weight(b) - self.weight(a)

class UnionFind:
    def __init__(self,N):
        self.root = list(range(N+1))
        self.size = [1] * (N+1)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

    def sz(self, x):
        return self.size[x]


if __name__ == "__main__":

    N,M,K = map(int, readline().split())
    A = [0] * (M+5)
    B = [0] * (M+5)
    C = [0] * (K+5)
    D = [0] * (K+5)
    for i in range(M):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        A[i] = a 
        B[i] = b 
    for i in range(K):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        C[i] = a 
        D[i] = b 
    uf = UnionFind(N)
    for i in range(M):
        uf.merge(A[i], B[i])

    arr = [[] for _ in range(N+2)]
    edge = [[] for _ in range(N+2)]
    for i in range(N):
        arr[uf.find_root(i)].append(i)
    
    for i in range(M):
        if uf.find_root(A[i]) == uf.find_root(B[i]):
            edge[uf.find_root(A[i])].append(i)
    
    for i in range(K):
        if uf.find_root(C[i]) == uf.find_root(D[i]):
            edge[uf.find_root(C[i])].append(i + M)
        

    ans = ["0"] * N
    for i in range(N):
        dd = {}
        if len(arr[i]) == 0:
            continue
        sz = uf.sz(i)
        for j, v in enumerate(arr[i]):
            dd[v] = j
        friends = [0] * (sz+2)
        for e in edge[i]:
            if e <= M-1:
                friends[dd[A[e]]] += 1
                friends[dd[B[e]]] += 1
            else:
                friends[dd[C[e-M]]] += 1
                friends[dd[D[e-M]]] += 1
        for v in arr[i]:
            res = sz - friends[dd[v]] - 1
            ans[v] = str(res)
    print(" ".join(ans))

Submission status: Accepted

Solution code:
# 参照 https://qiita.com/Kerzival/items/6923c2eb3b91be86f19f
class UnionFind:
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.find_root(x)
        y = self.find_root(y)
        # すでに同じ木に属していた場合
        if x == y :
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    # ノードxが属する木のサイズを返す
    def count(self, x):
        return -self.root[self.find_root(x)]


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

friend_count = [0] * (N + 1)
block_with = [[] for _ in range(N + 1)]
uf = UnionFind(N + 1)

for f in friend:
    friend_count[f[0]] += 1
    friend_count[f[1]] += 1
    uf.unite(f[0], f[1])

for b in block:
    block_with[b[0]].append(b[1])
    block_with[b[1]].append(b[0])

for i in range(1, N + 1):
    ans = uf.count(i) - friend_count[i] - 1
    for b in block_with[i]:
        if uf.is_same_group(i, b):
            ans -= 1
    if i > 1:
        print(" ", end="")
    print(ans, end="")

print()

Submission status: Accepted

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

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

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

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


import sys
input = sys.stdin.buffer.readline

n, m, k = map(int, input().split())
friend = UnionFind(n)
f_cnt = [0] * n
for _ in range(m):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	friend.unite(a, b)
	f_cnt[a] += 1
	f_cnt[b] += 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)
ans = []
for i in range(n):
	ret = friend.size(i) - f_cnt[i] - 1
	for j in block[i]:
		if friend.isSame(i, j):
			ret -= 1
	ans.append(ret)
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]
        self.sz = defaultdict(lambda:1)

    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:
            size = self.sz[s1]+self.sz[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
            s = self.find(x)
            self.sz[s] = size
            return True
        return False

    def size(self, x):
        s = self.find(x)
        return self.sz[s]
N,M,K = map(int,input().split())
u = UnionFind(N)
friend = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)
    u.union(A-1,B-1)
block = [[] for _ in range(N)]
for i in range(K):
    C,D = map(int,input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)
ans = [0]*N
for i in range(N):
    ans[i] = u.size(i)-1
    for f in friend[i]:
        if u.find(i)==u.find(f):
            ans[i] -= 1
    for b in block[i]:
        if u.find(i)==u.find(b):
            ans[i] -= 1
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))  # 無向グラフ


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


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

    # ブロック関係
    block = Graph(N)
    for c, d in zip(C, D):
        block.add_edge(c-1, d-1)

    # 友好関係
    friendUF = UnionFind(N)
    degree = [0]*N
    for a, b in zip(A, B):
        friendUF.unite(a-1, b-1)
        degree[a-1] += 1
        degree[b-1] += 1

    # 友好的に連結している数を調べる
    group = defaultdict(int)
    for i in range(N):
        group[friendUF.root(i)] += 1

    ans = []
    for i in range(N):
        # iの連結している個数 - 次数 - 1 （自身を除く）
        # print(" -- {} --".format(i))
        # print(group[friendUF.root(i)], degree[i])
        ans.append(group[friendUF.root(i)] - degree[i] - 1)
        # ブロックを考慮する
        for dest, _ in block.E[i]:
            if friendUF.same(dest, i):
                ans[-1] -= 1
    print(*ans, sep=" ")
    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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
N,M,K = map(int,input().split())
C = UnionFind(N)
F = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    C.Unite(a,b)
    F[a]+=1
    F[b]+=1
B = [[] for i in range(N+1)]
for h in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
A = [0]*N
for n in range(1,N+1):
    all_ = C.Count(n)
    B_cnt = 0
    for b in B[n]:
        if C.isSameGroup(n,b):B_cnt+=1
    A[n-1] = all_ - B_cnt - F[n] - 1
print(*A)

Submission status: Accepted

Solution code:
from collections import Counter
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
    N,M,K = list(map(int,input().split()))
    counter = Counter()
    uf = UnionFind(N+1)
    for i in range(M):
        a,b = list(map(int,input().split()))
        counter.update((a,b))
        uf.union(a,b)
    
    ans = [0]*(N+1)

    for i in range(1,N+1):
        ans[i] = uf.size(i)-counter[i]-1
    for i in range(K):
        a,b = list(map(int,input().split()))
        if uf.same(a,b):
            ans[a] -= 1
            ans[b] -= 1
    
    for i in range(1,N):
        print(ans[i] if 0<=ans[i] else 0,end=" ")
    print(ans[N] if 0<=ans[i] else 0)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

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

import sys
input=sys.stdin.buffer.readline

n,m,k=map(int,input().split())
friend=UnionFind(n)
f_cnt=[0]*n
for _ in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	friend.unite(a,b)
	f_cnt[a]+=1
	f_cnt[b]+=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)
ans=[]
for i in range(n):
	ret=friend.size(i)-f_cnt[i]-1
	for j in block[i]:
		if friend.isSame(i,j):
			ret-=1
	ans.append(ret)
print(*ans)