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:
# -*- coding: utf-8 -*-

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        self.number = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)
            self.number.append(1)

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

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

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

    def union_number(self, x):
        x = self.find(x)
        return self.number[x]

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

uf_tree = UnionFindTree(N)
for (a, b) in AB:
    a -= 1
    b -= 1
    uf_tree.unite(a, b)

candidates = []
for n in range(N):
    candidates.append(uf_tree.union_number(n) - 1)

for (a, b) in AB:
    a -= 1
    b -= 1
    candidates[a] -= 1
    candidates[b] -= 1

for (c, d) in CD:
    c -= 1
    d -= 1
    if uf_tree.same(c, d):
        candidates[c] -= 1
        candidates[d] -= 1

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

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

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
uf = UnionFind(N)
ans = [0]*N
not_friend_candidates = [1]*N #自分自身
nfc = not_friend_candidates
for _ in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
    nfc[A-1] += 1
    nfc[B-1] += 1
for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C-1, D-1):
        nfc[C-1] += 1
        nfc[D-1] += 1
ans = [uf.size(i)-nfc[i] for i in range(N)]
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 same(self, x, y):
        return self.find(x) == self.find(y)

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


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    u = UnionFind(n)
    f_cnts = [0] * n
    b_cnts = [0] * n

    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        u.union(x, y)
        f_cnts[x] += 1
        f_cnts[y] += 1

    for _ in range(k):
        x, y = map(lambda x: int(x) - 1, input().split())
        if u.same(x, y):
            b_cnts[x] += 1
            b_cnts[y] += 1

    cnts = ((u.size(i) - f_cnts[i] - b_cnts[i] - 1) for i in range(n))
    print(' '.join(map(str, cnts)))

Submission status: Accepted

Solution code:
class unionFind():
  def __init__(self,n):
    self.size = 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 grpsize(self, x):
    return -self.parents[self.find(x)]
  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.size) if self.find(i) == root]
  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
import sys
sys.setrecursionlimit(4100000)

line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0])-1, int(line[1])-1]

nconnected = [0]*nPerson
for i in friends:
    nconnected[i[0]] += 1
    nconnected[i[1]] += 1
  
  
blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0])-1, int(line[1])-1]

uf = unionFind(nPerson)
for i in friends:
  uf.union(i[0],i[1])

nblocked = [0]*nPerson
for i in blocks:
  if uf.find(i[0]) == uf.find(i[1]):
    nblocked[i[0]] += 1
    nblocked[i[1]] += 1
  
res = ""
for i in range(nPerson):
  res += str(uf.grpsize(i)-nconnected[i] -nblocked[i]-1) + " "

print(res)

Submission status: Accepted

Solution code:
import time, sys
sys.setrecursionlimit(int(1e7))

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.add(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = set()
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

Submission status: Accepted

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

n,m,k=map(int, input().split())  
friend=[[] for _ in range(n)]

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

par=[None]*n
frmember=defaultdict(int)

def dfs(v):
    if par[i]==None:
        par[v]=v
        frmember[par[v]]+=1
    for f in friend[v]:
        if par[f]==None:
            par[f]=par[v]
            frmember[par[v]]+=1
            dfs(f)

for i in range(n):
    if par[i]==None:
        dfs(i)

ans=[0]*n
for i in range(n):
    ans[i]+=frmember[par[i]]-len(friend[i])-1

for i in range(k):
    a,b=map(int, input().split()) 
    if par[a-1]==par[b-1]:
        ans[a-1]-=1
        ans[b-1]-=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 same(self, x, y):
        return self.find(x) == self.find(y)

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


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    u = UnionFind(n)
    f_cnt = [0] * n
    b_cnt = [0] * n

    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
        f_cnt[a - 1] += 1
        f_cnt[b - 1] += 1

    for _ in range(k):
        c, d = map(int, input().split())
        if u.same(c - 1, d - 1):
            b_cnt[c - 1] += 1
            b_cnt[d - 1] += 1

    print(*[(u.size(i) - f_cnt[i] - b_cnt[i] - 1) for i in range(n)])

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())
Friend_Net = UnionFind(N)
Block = [[] for i in range(N)]
friend = [0] * N

for i in range(M):
    A, B = map(int, input().split())
    friend[A-1] += 1
    friend[B-1] += 1
    Friend_Net.union(A-1, B-1)

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

for i in range(N):
    ans = Friend_Net.size(i) - friend[i]
    for b in Block[i]:
        if Friend_Net.same(i, b):
            ans -= 1
    print(ans-1)

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())
Friend_Net = UnionFind(N)
Friend = [[] for i in range(N)]
Block = [[] for i in range(N)]
friend = [0] * N

for i in range(M):
    A, B = map(int, input().split())
    friend[A-1] += 1
    friend[B-1] += 1
    Friend[A-1].append(B-1)
    Friend[B-1].append(A-1)
    Friend_Net.union(A-1, B-1)

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

for i in range(N):
    ans = Friend_Net.size(i) - friend[i]
    for b in Block[i]:
        if Friend_Net.same(i, b):
            ans -= 1
    print(ans-1)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
a_m, b_m = [], []
c_k, d_k = [], []
def minus(x):
    return int(x)-1

friends_list = [[] for i in range(n)]
block_list = [[] for i in range(n)]
for i in range(m):
    a_m.append(0)
    b_m.append(0)
    a_m[i], b_m[i] = map(minus, input().split())
    friends_list[a_m[i]].append(b_m[i])
    friends_list[b_m[i]].append(a_m[i])
for i in range(k):
    c_k.append(0)
    d_k.append(0)
    c_k[i], d_k[i] = map(minus, input().split())
    block_list[c_k[i]].append(d_k[i])
    block_list[d_k[i]].append(c_k[i])

# どのグループに属しているかを返す
def find(x):
    if parents[x] < 0:
        return x
    else:
        return find(parents[x])

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x
    return 0

def union_size(x):
    return -parents[find(x)]

def blocks_in_union(x):
    count = 0
    for block in block_list[x]:
        if find(x) == find(block):
            count += 1
    return count

parents =[ -1 for i in range(n)]
for i in range(m):
    union(a_m[i], b_m[i])
for i in range(n):
    print(union_size(i)-1-len(friends_list[i])-blocks_in_union(i), end=' ')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]
rank = [0]*(N+1)

def union(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return
    if rank[x]<rank[y]:
        parent[x]=y
    else:
        parent[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x]= find(parent[x])
        return parent[x]





for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1


kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def 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]
        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):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.union(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block):
            ans[iam] -= 1

print(*ans, sep=' ')

Submission status: Accepted

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

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

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

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

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


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる
C, D = [0] * K, [0] * K  # 入力時に 0-index に合わせる

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
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

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

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(direct[i]) - 1
print(*ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #各ノードの親番号
        self.rank = [0] * (n) #各ノードのランク（木の高さ）
        self.root = [-1]*(n+1) # -（各ノードの属するグループの要素数）

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            # node = [x]
            # cur = node[0]
            # while self.par[cur] != cur:
            #     cur = self.par[cur]
            #     node.append(self.par[cur])
            
            # for n in node:
            #     self.par[n] = cur
            
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
                
    # グループ数
    def groupsize(self):
        cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                cnt += 1
        return cnt

    # xの属すグループの要素数
    def size(self, x):
        return -self.root[self.find(x)]
    
    # xの属すグループの要素リスト
    def members(self, x):
        ret = []
        rootNode = self.find(x)
        for i in range(len(self.par)):
            if self.find(i) == rootNode:
                ret.append(i)
        return ret
    
    # ルートノードのリストを取得
    def get_roots(self):
        ret = []
        for i,x in enumerate(self.par):
            if x==i:
                ret.append(i)
        return ret
    
    # 各グループ毎の要素リストを取得
    def all_members(self):
        L = len(self.par)
        roots = self.get_roots()
        namedict = [0]*L
        for i,r in enumerate(roots):
            namedict[r] = i
        
        
        ret = [[] for _ in range(len(roots))]
        for i in range(len(self.par)):
            p = namedict[self.find(i)]
            ret[p].append(i)
        return ret
            
    

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)
for a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N
 
for group in uf.all_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1
 
for c,d in CD:
    if uf.same_check(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
 
print(*ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #各ノードの親番号
        self.rank = [0] * (n) #各ノードのランク（木の高さ）
        self.root = [-1]*(n+1) # -（各ノードの属するグループの要素数）

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            node = [x]
            cur = node[0]
            while self.par[cur] != cur:
                cur = self.par[cur]
                node.append(self.par[cur])
            
            for n in node:
                self.par[n] = cur
            
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
                
    # グループ数
    def groupsize(self):
        cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                cnt += 1
        return cnt

    # xの属すグループの要素数
    def size(self, x):
        return -self.root[self.find(x)]
    
    # xの属すグループの要素リスト
    def members(self, x):
        ret = []
        rootNode = self.find(x)
        for i in range(len(self.par)):
            if self.find(i) == rootNode:
                ret.append(i)
        return ret
    
    # ルートノードのリストを取得
    def get_roots(self):
        ret = []
        for i,x in enumerate(self.par):
            if x==i:
                ret.append(i)
        return ret
    
    # 各グループ毎の要素リストを取得
    def all_members(self):
        L = len(self.par)
        roots = self.get_roots()
        namedict = [0]*L
        for i,r in enumerate(roots):
            namedict[r] = i
        
        
        ret = [[] for _ in range(len(roots))]
        for i in range(len(self.par)):
            p = namedict[self.find(i)]
            ret[p].append(i)
        return ret
            
    

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)
for a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N
 
for group in uf.all_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1
 
for c,d in CD:
    if uf.same_check(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
 
print(*ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #各ノードの親番号
        self.rank = [0] * (n) #各ノードのランク（木の高さ）
        self.root = [-1]*(n+1) # -（各ノードの属するグループの要素数）

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            node = [x]
            cur = node[0]
            while self.par[cur] != cur:
                cur = self.par[cur]
                node.append(self.par[cur])
            
            for n in node:
                self.par[n] = cur
            
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
                
    # グループ数
    def groupsize(self):
        cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                cnt += 1
        return cnt

    # xの属すグループの要素数
    def size(self, x):
        return -self.root[self.find(x)]
    
    # xの属すグループの要素リスト
    def members(self, x):
        ret = []
        rootNode = self.find(x)
        for i in range(len(self.par)):
            if self.find(i) == rootNode:
                ret.append(i)
        return ret
    
    # ルートノードのリストを取得
    def get_roots(self):
        ret = []
        for i,x in enumerate(self.par):
            if x==i:
                ret.append(i)
        return ret
    
    # 各グループ毎の要素リストを取得
    def all_members(self):
        roots = self.get_roots()
        namedict = {}
        for i,r in enumerate(roots):
            namedict[r] = i            
        ret = [[] for _ in range(len(roots))]
        for i in range(len(self.par)):
            p = namedict[self.find(i)]
            ret[p].append(i)
        return ret
            
    

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)
for a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N
 
for group in uf.all_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1
 
for c,d in CD:
    if uf.same_check(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
 
print(*ans)