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():
  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())
AB = [list(map(int, input().split())) for _ in range(m)]
CD = [list(map(int, input().split())) for _ in range(k)]

uf = UnionFind(n)
fre = [0] * n
for a, b in AB:
  fre[a - 1] += 1
  fre[b - 1] += 1
  uf.union(a - 1, b - 1)

blo = [0] * n
for c, d in CD:
  if uf.same(c - 1, d - 1):
    blo[c - 1] += 1
    blo[d - 1] += 1

rs = uf.roots()
cnt = {r: uf.size(r) for r in rs}

ans = []
for i in range(n):
    r = uf.find(i)
    ans.append(cnt[r] - fre[i] - blo[i] - 1)
print(*ans)

Submission status: Accepted

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

import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)

    ccmembs = []
    ccmap = [-1] * n
    def color_component(ccid, root):
        stack = [root]
        ccmap[root] = ccid
        nmemb = 1
        while len(stack) > 0:
            u = stack.pop()
            for v in g[u]:
                if ccmap[v] < 0:
                    ccmap[v] = ccid
                    nmemb += 1
                    stack.append(v)
        return nmemb

    for u in range(n):
        if ccmap[u] < 0:
            ccmembs.append(color_component(len(ccmembs), u))

    for u in range(n):
        c = (ccmembs[ccmap[u]]
                - sum(1 for v in g[u] if ccmap[u] == ccmap[v])
                - sum(1 for v in bg[u] if ccmap[u] == ccmap[v])
                - 1)
        print(c, end=(' ' if u != n - 1 else '\n'))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ
        self.blocksize = [0] * N

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def block(self, x, y):
        if not self.has_same_parent(x, y):
            return
        self.blocksize[x] += 1
        self.blocksize[y] += 1

    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.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

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

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

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


N, M, K = MI()
uf = UnionFind(N)
nl = [set() for _ in range(N)]
for _ in range(M):
    A, B = MI()
    nl[A - 1].add(B - 1)
    nl[B - 1].add(A - 1)
    uf.unite(A - 1, B - 1)

for _ in range(K):
    C, D = MI()
    uf.block(C - 1, D - 1)


ans = []
for i in range(N):
    a = uf.component_size(i) - len(nl[i]) - uf.blocksize[i] - 1
    ans.append(str(a))
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    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 same_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:
            return 
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n)
ans_li = [-1 for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    ans_li[a] -= 1
    ans_li[b] -= 1
for i in range(k):
    a,b = map(int, input().split())
    if u.find(a) == u.find(b):
        ans_li[a] -= 1
        ans_li[b] -= 1
for i in range(1,n+1):
    ans_li[i] += u.getsize(i)
    print(ans_li[i], end = " ")

Submission status: Accepted

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

    def find(self, x):  # xの親を返す
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[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.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

# 全部 0-indexed に合わせる

g_direct =[[] for _ in range(N)]
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    g_direct[A[i]].append(B[i])
    g_direct[B[i]].append(A[i])
    uf.unite(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]):  # 同じ連結成分内にない場合は無視してもよい
        g_direct[C[i]].append(D[i])
        g_direct[D[i]].append(C[i])


ans = [0] * N
# i と j が同じ連結成分に含まれて、 i と j が友達関係もしくはブロック関係にあるような j の個数
for i in range(N):
    ans[i] = uf.group_size(i) - len(g_direct[i]) - 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)

    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=list(map(int,input().split()))

candFriends=UnionFind(n)
elim=[0]*n

for i in range(m):
    a,b=list(map(lambda x:int(x)-1,input().split()))
    candFriends.union(a,b)
    
    elim[a]-=1
    elim[b]-=1

for i in range(k):
    c,d=list(map(lambda x:int(x)-1,input().split()))

    rootc=candFriends.find(c)
    rootd=candFriends.find(d)

    if rootc==rootd:
        elim[c]-=1
        elim[d]-=1


print(' '.join([str(candFriends.size(i)+elim[i]-1) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind_size:
    def __init__(self, n):
        # 初期状態は全要素が根なので、親は自分自身
        self.par = [i for i in range(n+1)]
        # 集団の要素数(size)を格納する(初期は全て1)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        # 根までたどったらその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索過程で親を書き換える(圧縮経路)
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    def unite(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # サイズを比較し、小さい方を大きい方に繋げる
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    N,M,K = map(int, readline().split())

    uf = UnionFind_size(N+1)
    F = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        F[a].append(b)
        F[b].append(a)
        uf.unite(a, b)
    
    B = [[] for _ in range(N+1)]
    for _ in range(K):
        c,d = map(int, readline().split())
        B[c].append(d)
        B[d].append(c)


    ans = []
    for i in range(1,N+1):
        tmp = 0
        tmp += uf.get_size(i) - 1
        tmp -= len(F[i])
        for j in B[i]:
            if uf.same_check(i, j):
                tmp -= 1
        ans.append(tmp)
    
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

N, M, K = map(int, input().split())
friends = [set(map(int, input().split())) for _ in range(M)]
blocks = [set(map(int, input().split())) for _ in range(K)]

ans = [0] * N
uf = UnionFind(N)
for a, b in friends:
    uf.union(a - 1, b - 1)
    ans[a - 1] -= 1
    ans[b - 1] -= 1
    
for c, d in blocks:
    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)

Submission status: Accepted

Solution code:
# ABC157 - D

from collections import Counter

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

fn = [1]*N
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

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 unite(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 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 size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        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):#print()での表示用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m,k=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(m)]
    B=[tuple(map(int,input().split())) for _ in range(k)]
   

    uf=UnionFind(n)
    for a,b in F:
        a-=1
        b-=1
        uf.unite(a,b)
      
    cnt=[0]*n
    for i in range(n):
        cnt[i]=uf.size(i)-1
    
    for a,b in F:
        a-=1
        b-=1
        if uf.same(a,b):
            cnt[a]-=1
            cnt[b]-=1
    
    for c,d in B:
        c-=1
        d-=1
        if uf.same(c,d):
            cnt[c]-=1
            cnt[d]-=1
    print(*cnt)
   
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 FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  cnt[a]+=1
  cnt[b]+=1
  t.Unite(a,b)
for _ in range(k):
  a,b=map(int,input().split())
  if t.isSameGroup(a,b)==True:
    cnt[a]+=1
    cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
  ans[i]=(t.Count(i)-1)-cnt[i]
print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

N, M, K = map(int, readline().split())
m = map(int,read().split())
fb = list(zip(m,m))

AB = fb[:M]
CD = fb[M:]
uf = UnionFind(N+1)
friends = [[] for i in range(N+1)]
for a, b in AB:
    uf.union(a, b)
    friends[a].append(b)
    friends[b].append(a)

blocks = [[] for i in range(N+1)]
for c, d in CD:
    blocks[c].append(d)
    blocks[d].append(c)

ans = []
for i in range(1, N+1):
    same_tree_size = uf.size(i)
    same_tree_block = 0
    for x in blocks[i]:
        same_tree_block += uf.same(i, x)
    n_friends = len(friends[i])
    # 「同じグループに所属する人の数」 には、iと直接友達の人、
    # iがブロックしている人i本人も含まれている
    # よって、以下でiの友達候補の人数が分かる
    # 同じグループに所属する人の数 - 同じグループ内にいるiがブロックしている人の数
    #   - 友達の数 - 1(自分)
    ans.append(str(same_tree_size - same_tree_block - n_friends - 1))

print(' '.join(ans))

Submission status: Accepted

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

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

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = parent
			while True:
				tmp = self.groups[root]
				if tmp == root:
					break
				root = tmp
			
			while i != root:
				tmp = self.groups[i]
				self.groups[i] = root
				i = tmp
			
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		while parent != root:
			self.groups[i] = root
			i = parent
			parent = self.groups[i]
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def counts(self):
		table = [None] * len(self.groups)
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if table[g] != None:
				table[g] += 1
			else:
				table[g] = 1
		
		ret = [0] * len(self.groups)
		
		for i in range(len(self.groups)):
			ret[i] = table[self.get_root(i)]
		
		return ret
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]


groups = UnionFind(N)
minus_list = [0] * N

for _ in range(M):
	a, b = map(lambda x: int(x) - 1, input().split())
	groups.combine(a, b)
	minus_list[a] -= 1
	minus_list[b] -= 1

for _ in range(K):
	c, d = map(lambda x: int(x) - 1, input().split())
	if groups.in_same_group(c, d):
		minus_list[c] -= 1
		minus_list[d] -= 1

counts = groups.counts()

print(" ".join((str(counts[i] + minus_list[i] - 1) for i in range(N))))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import Counter

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

fn = [1]*N
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
import sys

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, rank, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return

    if rank[x] >= rank[y]:
        uft[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        uft[x] = y

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(int)
    block = defaultdict(int)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    rank = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, rank, a, b)
        friend[a] += 1
        friend[b] += 1
    for j in range(k):
        c, d = map(int, input().split())
        if not same(uft, c, d):
            continue
        block[c] += 1
        block[d] += 1
    for i in range(1, n+1):
        root(uft, i)
    c = Counter(uft)
    return [c[uft[i]]-block[i]-friend[i]-1 for i in range(1, n+1)]

print(*answer())

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)
    


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

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

for _ in range(K):
    a,b = map(int, input().split())
    if uf.same(a-1,b-1):
        block[a-1] += 1
        block[b-1] += 1

result = [uf.size(i) - friend[i] - block[i] - 1 for i in range(N)]
print(' '.join(map(str, result)))

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n, m, k = [int(s) for s in input().strip().split()]
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = [int(s) for s in input().strip().split()]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    
    groups = [-1] * n
    for i in range(n):
        if groups[i] < 0:
            groups[i] = i
            q = [i]
            for j in q:
                for v in adj[j]:
                    if groups[v] < 0:
                        groups[v] = i
                        q.append(v)
    cnt = Counter(groups)

    result = [cnt[groups[i]] - len(adj[i]) - 1 for i in range(n)]
    for _ in range(k):
        c, d = [int(s) for s in input().strip().split()]
        if groups[c - 1] == groups[d - 1]:
            result[c - 1] -= 1
            result[d - 1] -= 1
    print(" ".join(str(x) for x in result))


main()

Submission status: Accepted

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

# Union Find

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1]*(N+1)


friend_list = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    unite(A,B)
    friend_list[A].append((B))
    friend_list[B].append((A))

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

anslist = [0]*(N)
for i in range(1,N+1):

    block_and_connect = 0
    for hito in block_list[i]:
        if same(hito,i):
            block_and_connect += 1
    ans = size(i) - 1 - len(friend_list[i]) - block_and_connect
    anslist[i-1] = ans
print(*anslist)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import Counter

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

fn = defaultdict(lambda: 1)
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

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

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

    def roots(self):
        return [i for i, x in enumerate(self.root) 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 size(self, x):
        return -self.root[self.Find_Root(x)]


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

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

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

res = []
for _ in range(n):
    res.append( [0, -1] )
ures = []

for i in range(n):
    res[i][0] = uf.size(i) - directcount[i] -1
    res[i][1] = uf.Find_Root(i)
#print(res)


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


print(" ".join(list(map(lambda x: str(x[0]), res))))