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, nodes):
        self.sets = [None] * len(nodes)
        self.sizes = [1] * len(nodes)

    def find(self, a):
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [None] * n
    uf = UnionFind(users)

    friendships = [0 for i in range(n)]
    blockships = [0 for i in range(n)]

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        a -= 1
        b -= 1
        friendships[a] += 1
        friendships[b] += 1
        uf.union(a, b)
        uf.find(a)
        uf.find(b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        a -= 1
        b -= 1
        if uf.connected(a, b):
            blockships[a] += 1
            blockships[b] += 1

    res = [0] * n
    for i in range(n):
        all_connections = uf.size(i)
        existing = friendships[i]
        blocked = blockships[i]
        res[i] = all_connections - 1 - existing - blocked

    print(" ".join([str(u) for u in res]))

Submission status: Accepted

Solution code:
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 isSameGroup(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())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = UnionFind(n+1)


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    uni.Unite(a, b)

for i in range(k):
    c, d = cd[i]
    if uni.isSameGroup(c,d):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    result.append(uni.Count(i)-con[i])
print(*result)

Submission status: Accepted

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

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

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

        if abs(x) < abs(y): 
            x, y = y, x 
        self.rank[x] += self.rank[y]
        self.rank[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.rank[self.find(x)]

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

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

ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i)-1-friend[i]
    for j in block[i]:
        if uf.same(i,j):
            ans[i] -= 1
    ans[i] = str(ans[i])
    
print(" ".join(ans))

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
ans=[0 for i in range(N)]
  
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

    def 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):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  ans[a-1]-=1;ans[b-1]-=1
    
for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    ans[c-1]-=1;ans[d-1]-=1
    
for i in range(N):
  ans[i]+=uf.size(i)-1
  print(ans[i],end=" ")

Submission status: Accepted

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


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を見てくっつける方を決める
      #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 isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  
F=[[] for i in range(N)]
B=[[] for i in range(N)]
union=UnionFind(N)
for i in range(M):
  a, b=map(int, input().split())
  union.Unite(a-1,b-1)
  F[a-1].append(b-1)
  F[b-1].append(a-1)
  
for i in range(K):
  c, d=map(int, input().split())
  B[c-1].append(d-1)
  B[d-1].append(c-1)
  
ans=[]
for i in range(N):
  x=union.Count(i)-1-len(F[i])
  for j in range(len(B[i])):
    if union.isSameGroup(i, B[i][j]):
      x-=1
  ans.append(str(x))
  
print(" ".join(ans))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


n, m, k = map(int, input().split())
friends = {}
blocks = {}
for i in range(n):
    friends[i] = 0
    blocks[i] = 0
uf_friends = UnionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    friends[x] += 1
    friends[y] += 1
    uf_friends.union(x, y)

for i in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if (uf_friends.same(x, y)):
        blocks[x] += 1
        blocks[y] += 1

ans = []
for i in range(n):
    ans.append(str(uf_friends.size(i) - friends[i] - blocks[i] - 1))

print(' '.join(ans))

Submission status: Accepted

Solution code:
# n, m, k = map(int, input().split())
# t = []
# for i in range(n):
#     t.append([1] * n)
# for i in range(m + k):
#     a, b = map(int, input().split())
#     t[a - 1][b - 1] = 0
#     t[b - 1][a - 1] = 0
# for i in range(n):
#     for j in range(n):
#         if (i == j):
#             t[i][j] = 0
# ans = ''
# for i in range(n):
#     if (i == n - 1):
#         ans += str(sum(t[i]))
#     else:
#         ans += str(sum(t[i])) + ' '
# print(ans)


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


n, m, k = map(int, input().split())
friends = {}
blocks = {}
for i in range(n):
    friends[i] = 0
    blocks[i] = 0
uf_friends = UnionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    friends[x] += 1
    friends[y] += 1
    uf_friends.union(x, y)

for i in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if (uf_friends.same(x, y)):
        blocks[x] += 1
        blocks[y] += 1

ans = []
for i in range(n):
    ans.append(str(uf_friends.size(i) - friends[i] - blocks[i] - 1))

print(' '.join(ans))

Submission status: Accepted

Solution code:
#02:08
#BFS
n,m,k = map(int,input().split())
peer = [[] for _ in range(n)]
num = [1 for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
root = [i for i in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if seen[i] == 1:
    continue
  seen[i] = 1
  now = [i]
  tmp = 1
  while now:
    last = now
    now = []
    for x in last:
      for y in peer[x]:
        if seen[y] == 0:
          seen[y] = 1
          now.append(y)
          root[y] = i
          tmp += 1
  cnt[i] = tmp
#print(root)
#print(cnt)
for i in range(n):
  cnt[i] = cnt[root[i]]
#print(cnt)
for i in range(n):
  cnt[i] -= num[i]
#print(cnt)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    cnt[a] -= 1
    cnt[b] -= 1
print(' '.join(map(str,cnt)))

Submission status: Accepted

Solution code:
# Disjoint Set: Union Find Tree
class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 最初は全てが根であるとして初期化        
        self.parent = [-1] * N  # idxが各ノードのid, 値がそのノードの親ノードのid

    def find(self, x):  # ノードのidを受け取って一番上の親ノードのidを帰す
        if (self.parent[x] < 0):
            return x
        self.parent[x] = self.find(self.parent[x])  # 経由したノードすべての親を上書き（経路圧縮）
        return self.parent[x]

    def unite(self, x, y): # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        rx = self.find(x) # xの根をrx
        ry = self.find(y) # yの根をry
        if (rx == ry): # xとyの根が同じ(=同じ木にある)時はそのまま
            return False

        if self.parent[rx] > self.parent[ry]:
            rx, ry = ry, rx
 
        self.parent[rx] += self.parent[ry]
        self.parent[ry] = rx

        return True
    
    def size(self, x):
        return -self.parent[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.parent) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
N, M, K = map(int, input().split())
ds = UnionFind(N+1)
num = [0]*(N+1)
G = [[] for i in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    ds.unite(x, y)
for _ in range(K):
    x, y = map(int, input().split())
    if ds.same(x,y) == True:
        G[x].append(y)
        G[y].append(x)
for i in range(1,N+1):
    print(ds.size(i) - len(G[i])-1,end=" ")

Submission status: Accepted

Solution code:
#01:55
#UnionFind最適化に向けた実験
n,m,k = map(int,input().split())
cnt = [1 for _ in range(n)]
pre = [i for i in range(n)]
num = [1 for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = []
  B = []
  while a != pre[a]:
    a = pre[a]
    A.append(a)
  while b != pre[b]:
    b = pre[b]
    B.append(b)
  if a != b:
    if cnt[a] >= cnt[b]:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
      cnt[a] += cnt[b]
      cnt[b] = 0
    else:
      pre[a] = b
      for aa in A:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
      cnt[b] += cnt[a]
      cnt[a] = 0
#print(pre)
#print(cnt)
root = []
ans = []
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(I)
  ans.append(cnt[I]-num[i])
#print(root)
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


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 isSameGroup(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, *ABCD = map(int, read().split())
AB = ABCD[:M * 2]
CD = ABCD[M * 2:]
F = UnionFind(N)
friend = [[] for _ in range(N + 1)]
for A, B in zip(*[iter(AB)] * 2):
    F.Unite(A, B)
    friend[A].append(B)
    friend[B].append(A)

block = [[] for _ in range(N + 1)]
for C, D in zip(*[iter(CD)] * 2):
    block[C].append(D)
    block[D].append(C)

answer = []
for i, n in enumerate(map(len, friend[1:]), 1):
    cnt = F.Count(i) - 1 - n
    for j in block[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    answer.append(cnt)

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

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda: map(int, stdin.readline().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)]

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

tree_f=[[] for i in range(n+1)]
tree_g=[[] for i in range(n+1)]

uf=UnionFind(n+1)

for i in range(m):
  a,b=nii()
  tree_f[a].append(b)
  tree_f[b].append(a)
  uf.union(a,b)

for i in range(k):
  a,b=nii()
  if uf.find(a)==uf.find(b):
    tree_g[a].append(b)
    tree_g[b].append(a)

ans=[uf.size(i)-len(tree_f[i])-len(tree_g[i])-1 for i in range(1,n+1)]
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.size = [1] * n
    self.rank = [1] * n
    
  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]
  
  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
        self.size[rj] += self.size[ri]
      else:
        self.parent[rj] = ri
        self.size[ri] += self.size[rj]
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1


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

n_friend = [1 for _ in range(n)]
block = [[] for _ in range(n)]
friendship = UnionFind(n)

for _ in range(m):
  a, b = map(int, input().split())
  n_friend[a-1] += 1
  n_friend[b-1] += 1
  friendship.unite(a-1, b-1)
  
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):
  r = friendship.find(i)
  cand = friendship.size[r] - n_friend[i]
  for j in block[i]:
    if r == friendship.find(j):
      cand -= 1
  print(cand, end=' ')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


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 isSameGroup(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, *ABCD = map(int, read().split())
AB = ABCD[:M * 2]
CD = ABCD[M * 2:]
F = UnionFind(N)
friend = [[] for _ in range(N + 1)]
for A, B in zip(*[iter(AB)] * 2):
    F.Unite(A, B)
    friend[A].append(B)
    friend[B].append(A)

block = [[] for _ in range(N + 1)]
for C, D in zip(*[iter(CD)] * 2):
    block[C].append(D)
    block[D].append(C)

answer = []
for i in range(1, N + 1):
    cnt = F.Count(i) - 1
    for j in block[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    cnt -= len(friend[i])
    answer.append(cnt)

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

Submission status: Accepted

Solution code:
# UnionFindでつなげていく
# [所属する木の頂点数]-[1（自分）]-[自分とブロック関係にある人の数]

# UnionFind
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 show_parents(self):
      print(self.parents)

# ここまでUnionFind
N,M,K=map(int,input().split())

UF=UnionFind(N)
from collections import defaultdict
dic=defaultdict(set)
friends=[0]*N
for i in range(M):
  a,b=map(int,input().split())
  UF.union(a-1,b-1)
  friends[a-1]+=1
  friends[b-1]+=1

for i in range(N):
  dic[UF.find(i)].add(i)

block=defaultdict(set)
for i in range(K):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)

# UF.show_parents()
# 同じ木に所属する人数のうち、ブロック関係にない人数
ans=[0]*N
for i in range(N):
  candi=dic[UF.find(i)]
  #print("i",candi,"block",block[i])
  ans[i]=len(candi)-friends[i]-1
  for b in block[i]:
    if UF.same(i,b):
      ans[i]-=1
  if ans[i]<0:
    ans[i]=0
print(*ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


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 isSameGroup(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, *ABCD = map(int, read().split())
AB = ABCD[:M * 2]
CD = ABCD[M * 2:]
F = UnionFind(N)
friend = [[] for _ in range(N + 1)]
for A, B in zip(*[iter(AB)] * 2):
    F.Unite(A, B)
    friend[A].append(B)
    friend[B].append(A)

block = [[] for _ in range(N + 1)]
for C, D in zip(*[iter(CD)] * 2):
    block[C].append(D)
    block[D].append(C)

answer = []
for i in range(1, N + 1):
    cnt = F.Count(i) - 1
    for j in block[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    for j in friend[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    answer.append(cnt)

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

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 isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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

def resolve():
    int1 = lambda x: int(x) - 1
    readline=sys.stdin.readline

    n,m,k=map(int, readline().strip().split())

    uf = UnionFind(n)

    exc=[0]*n

    for i in range(m):
        a,b=map(int1, readline().strip().split())
        uf.Unite(a,b)
        exc[a]+=1
        exc[b]+=1
    
    for i in range(k):
        a,b=map(int1, readline().strip().split())
        if uf.isSameGroup(a,b):
            exc[a]+=1
            exc[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-exc[i]
        rescnt.append(str(ri))
    
    print(" ".join(rescnt))

resolve()