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:
from collections import defaultdict


class UnionFind():
    # nはノードの数
    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]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = defaultdict(int)
for _ in range(M):  # 友達関係の数
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)
    friends[a] += 1
    friends[b] += 1
blocked = defaultdict(list)
for _ in range(K):  # ブロック関係の人数
    c, d = map(lambda x: int(x)-1, input().split())
    blocked[c].append(d)
    blocked[d].append(c)
ans = []
for i in range(N):
    # 同じグループの人数
    group_size = uf.size(i)
    # iと直接友達の人数
    i_frends = friends[i]
    # ブロック関係の人の中で、同じグループの人を数える
    cnt = 0
    for b in blocked[i]:
        if uf.same(i, b):
            cnt += 1
    ans.append(group_size - i_frends - cnt - 1)
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x): #連結しているもの
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y): #根が同じか判定する
        return self.root(x) == self.root(y)

    def unite(self, x, y): #くっつける
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x): #連結成分数
        return self.size[self.root(x)]

N,M,K=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for i in range(M):
    p,q=map(int,input().split())
    A.append(p-1)
    B.append(q-1)

for i in range(K):
    p,q=map(int,input().split())
    C.append(p-1)
    D.append(q-1)

Friend=Uf(N)
NG=[set() for _ in range(N)]

for i in range(M):
    Friend.unite(A[i],B[i])
    NG[A[i]].add(B[i])
    NG[B[i]].add(A[i])

for i in range(K):
    if Friend.same(C[i],D[i]): #同じ根なら・・・
        NG[C[i]].add(D[i])
        NG[D[i]].add(C[i])

for i in range(N):
    print(Friend.count(i)-len(NG[i])-1)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(500000)

class UF:
    #経路圧縮のみのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        if self.rnks[a_par] > self.rnks[b_par]:
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(self,n):
        par = self.find(n)
        return abs(self.parents[par])

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



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.length(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素xが属するグループの根を返す
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y): #要素xが属するグループと要素yが属するグループとを併合する
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

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

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

    def size(self,x): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素xが属するグループに属する要素をリストで返す
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]

    def roots(self): #すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x<0]

    def group_count(self): #グループの数を返す
        return len(self.roots())

    def all_group_members(self): #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

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

#print(list(uf.all_group_members().values())) #グループ一覧を表示

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

uf=UnionFind(n)
cnt=[0]*n

for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)
    cnt[x-1]+=1
    cnt[y-1]+=1
for _ in range(k):
    x,y=map(int,input().split())
    if uf.same(x-1,y-1):
        cnt[x-1]+=1
        cnt[y-1]+=1
    
for i in range(n):
    print(uf.size(i)-cnt[i]-1,end=" ")

Submission status: Accepted

Solution code:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

N,M,K=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for i in range(M):
    p,q=map(int,input().split())
    A.append(p-1)
    B.append(q-1)

for i in range(K):
    p,q=map(int,input().split())
    C.append(p-1)
    D.append(q-1)

Friend=Uf(N)
NG=[set() for _ in range(N)]

for i in range(M):
    Friend.unite(A[i],B[i])
    NG[A[i]].add(B[i])
    NG[B[i]].add(A[i])

for i in range(K):
    if Friend.same(C[i],D[i]):
        NG[C[i]].add(D[i])
        NG[D[i]].add(C[i])

for i in range(N):
    print(Friend.count(i)-len(NG[i])-1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.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)]

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

n,m,k = inpl()
ab = [inpl() for i in range(m)]
cd = [inpl() for i in range(k)]
uf = UnionFind(n)
fr = [[] for i in range(n)]
bl = [[] for i in range(n)]
for i in range(m):
    a,b = ab[i]
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
    uf.union(a-1,b-1)
for i in range(k):
    c,d = cd[i]
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)
# print(fr,bl)
for i in range(n):
    s = set()
    cnt = 0
    for j in fr[i]:
        s.add(j)
    for j in bl[i]:
        if uf.same(i,j) and not j in s:
            cnt += 1
    print(uf.size(i)-1 - len(s) - cnt)
# print(uf.members(0))

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self,n):
    self.parent=[i for i in range(n)] # 親要素のノード番号を格納 parent[x]==xの時そのノードは根
    self.rank=[0]*n # 木の高さを格納する
    self.count=0
    
  def root(self,x): # 根を返す
    if self.parent[x]==x: # 根ならその番号を返す
      return x
    else: # 根でないなら、親の要素で再検索 捜査の過程で親を書き換える
      self.parent[x]=self.root(self.parent[x])
      return self.root(self.parent[x])
    
  def is_same(self,x,y): # 同じ集合に属するか(根が同じか)判定
    return self.root(x)==self.root(y)
  
  def union(self,x,y): # 併合
    # 根を探す
    x=self.root(x)
    y=self.root(y)
    if x==y: return # 根が同じなら既に同じ集合なのでreturn
    # 木の高さを比較し、低い方から高い方に辺を張る
    if self.rank[x]<self.rank[y]:
      self.parent[x]=y
    else:
      self.parent[y]=x
      if self.rank[x]==self.rank[y]: self.rank[x]+=1
    self.count+=1
    
from collections import Counter
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)]

blocks=[set() for _ in range(n)]
for c,d in CD:
  c,d=c-1,d-1
  blocks[c].add(d)
  blocks[d].add(c)

friends=[0]*n
uf=UnionFind(n)
for a,b in AB:
  a,b=a-1,b-1
  friends[a]+=1
  friends[b]+=1
  if not uf.is_same(a,b): uf.union(a,b)
    
ctr=Counter()
for i in range(n):
  r=uf.root(i)
  ctr[r]+=1
  
ans=[]
for i in range(n):
  tmp=ctr[uf.root(i)]-friends[i]-1
  for b in blocks[i]:
    if uf.is_same(i,b): tmp-=1
  ans.append(tmp)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  query2 = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
    query2[a].append(b)
    query2[b].append(a)
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
      query2[a].append(b)
      query2[b].append(a)
  for i in range(n):
    print(uff.size(i)-1-len(query2[i]), end=" ")
solve()

Submission status: Accepted

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

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

V = [[] for _ in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  V[a].append(b)
  V[b].append(a)
# print(V)

L = [0 for _ in range(N)]
def dfs(u,l):
  L[u] = l
  for t in V[u]:
    if L[t] == 0:
      dfs(t,l)

l = 1
for i in range(N):
  if L[i] == 0:
    dfs(i,l)
    l += 1
#print(L)
C = {}
for ll in L:
  if ll in C:
    C[ll] += 1
  else:
    C[ll] = 1
#print(C)
ans = [C[L[i]]-1 for i in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  ans[a] -= 1
  ans[b] -= 1
for c,d in CD:
  c -= 1
  d -= 1
  if L[c] == L[d]:
    ans[c] -= 1
    ans[d] -= 1
print(*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)
    
N, M, K = map(int, input().split())
U = UnionFind(N)
ng = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    U.union(a-1, b-1)
    ng[a-1] += 1
    ng[b-1] += 1
for i in range(K):
    c, d = map(int, input().split())
    if U.same(c-1, d-1): 
        ng[c-1] += 1
        ng[d-1] += 1
li = []
for i in range(N):
    li.append(U.size(i)-ng[i]-1)
print(*li)

Submission status: Accepted

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

connected = [list(map(int, input().split())) for _ in range(M)]
blocked = [list(map(int, input().split())) for _ in range(K)]


class UnionFind(object):
    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)


uf = UnionFind(N)
num_remove = [0] * N

for a, b in connected:
    uf.union(a - 1, b - 1)

for a, b in connected:
    if uf.same(a - 1, b - 1):
        num_remove[a - 1] += 1
        num_remove[b - 1] += 1

for c, d in blocked:
    if uf.same(c - 1, d - 1):
        num_remove[c - 1] += 1
        num_remove[d - 1] += 1


ret = []
for i in range(N):
    ret.append(str(uf.size(i) - num_remove[i] - 1))


print(' '.join(ret))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d
# https://www.planeta.tokyo/entry/6193/

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
dir_or_blk = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dir_or_blk[a].append(b)
    dir_or_blk[b].append(a)
    uf.union(a, b)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d):
        dir_or_blk[c].append(d)
        dir_or_blk[d].append(c)

for i in range(N):
    ans = uf.size(i)-len(dir_or_blk[i])-1
    print(ans, end=" ")

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
N,M,K = map(int,input().split())
uf = UnionFind(N)

friend_cnt = [0] * N
for i in range(M):
    A,B = map(lambda x:int(x)-1,input().split())
    uf.union(A,B)
    friend_cnt[A]+=1
    friend_cnt[B]+=1
    
block_cnt = [0] * N
for i in range(K):
    C,D = map(lambda x:int(x)-1,input().split())
    if uf.same(C,D):
        block_cnt[C]+=1
        block_cnt[D]+=1
        
print(' '.join(map(lambda i:str(uf.size(i)-friend_cnt[i]-block_cnt[i]-1), range(N))))

Submission status: Accepted

Solution code:
# スペース区切りの整数入力
N,M,K = map(int, input().split())

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            fring[frnfrom] = []

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd] and frno[cc] != -1:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Submission status: Accepted

Solution code:
N, M, K = map(int,input().split())
uf = [-1 for _ in range(N)]
fc = [0] * N
bc = [0] * N
ans = [0] * N

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if uf[x] < 0:
        return x
    uf[x] = find(uf[x])
    return uf[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        x , y = y, x
    uf[y] += uf[x]
    uf[x] = y

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

for k in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -uf[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)
 
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]

def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    friends = [0] * n
    blocks = [0] * n
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1] += 1
        friends[b - 1] += 1
        uf.unite(a - 1, b - 1)
    for i in range(k):
        c, d = map(int, input().split())
        if uf.same(c - 1, d - 1):
            blocks[c - 1] += 1
            blocks[d - 1] += 1
    ans = [0] * n
    for i in range(n):
        ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
    print(*ans)      

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = set()
    ANS = {}
    for i in range(1, n + 1):
        if i in C:
            continue

        C.add(i)
        Cin = set()
        Cin.add(i)
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()) - Cin:
                Q.appendleft(f)
                C.add(f)
                Cin.add(f)

        for k in Cin:
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


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

    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 False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

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

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


d = DisjointSet(N)
friends = defaultdict(int)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai] += 1
    friends[Bi] += 1
blocking = defaultdict(list)
for Ci, Di in B:
    blocking[Ci].append(Di)
    blocking[Di].append(Ci)

ans = [0] * N
for i in range(N):
    ans[i] = d.size(i) - friends[i] - 1
    for b in blocking[i]:
        if d.same(i, b):
            ans[i] -= 1
print(' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Submission status: Accepted

Solution code:

class Unionfind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] = self.d[x] + self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.d[self.find(x)]

n, m, k = map(int, input().split())
dame = [set() for _ in range(n)]
uf = Unionfind(n)

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dame[a].add(b)
    dame[b].add(a)
    uf.unite(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    mem = uf.size(i) - 1
    mem -= len(dame[i])
    print(mem, end= " ")
print()