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 deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


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

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

q=deque([])
G=[]
visited=[0]*N
group=[-1]*N
idx=0
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    group[i]=idx
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                group[j]=idx
                q.append([j,c])
    G.append(c)
    idx+=1

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  group[i]==group[b]:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),end=" ")

Submission status: Accepted

Solution code:
#Union Find
n,m,k=map(int, input().split())

#xの根を求める, #parents[i]＝h　はiの親はjという意味、parents[i]=iはiが根という意味
def find(x):
    if parents[x] < 0: # 負なら根
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
#xとyの属する集合の併合
def unite(x,y):
    x = find(x) # x,yは根の番号にする。
    y = find(y)
    
    if x == y:
        return False
    else:
        if parents[x] > parents[y]: # sizeの大きいほうがx
            x,y = y,x
        parents[x] += parents[y]
        parents[y] = x
        return True

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


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

#初期化
#根なら-size,子なら親の頂点
parents=[-1]*n

friend = [set() for _ in range(n)]

for i in range(m): # 友達リスト
    a,b=map(int,input().split())
    unite(a-1,b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
    
a=[size(i)-len(friend[i])-1 for i in range(n)]

for i in range(k):
    c,d=map(int,input().split())
    if same(c-1,d-1):
        a[c-1]-=1
        a[d-1]-=1
print(*a)

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if uf.same(c, d):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)

Submission status: Accepted

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

import sys
input = sys.stdin.readline
N, M, K=map(int, input().split())

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

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

friend_or_block = [set() for _ in range(N)]
friends_chain = UnionFindTree(N)

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    friends_chain.unite(a, b)
    friend_or_block[a].add(b)
    friend_or_block[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if friends_chain.same(c, d):
        friend_or_block[c].add(d)
        friend_or_block[d].add(c)

print(' '.join(map(str, [friends_chain.count(i) - len(friend_or_block[i]) - 1 for i in range(N)])))

Submission status: Accepted

Solution code:


class DSU:
    def __init__(self, n):
        self.__parent = [i for i in range(n+1)]
        self.__size = [1 for _ in range(n+1)]
        self.n = n

    def parentOf(self,x):
        if self.__parent[x] != x:
            self.__parent[x] = self.parentOf(self.__parent[x])
        return self.__parent[x]
    
    def sizeOf(self,x):
        return self.__size[self.parentOf(x)]
    
    def makeUnion(self,x,y):
        p = self.parentOf(x)
        q = self.parentOf(y)
        if p==q:
            return
        if self.__size[p] < self.__size[q]:
            p,q = q,p
        self.__parent[q] = p
        #print("u",self.__size[p],self.__size[q])
        self.__size[p] += self.__size[q]
        #print(self.__size[p],self.__size[q])
    


if __name__ == "__main__":
    n,m,k = (int(x) for x in input().split())
    friendEdge = [ [int(x) for x in input().split()] for _ in range(m) ]
    enemyEdge = [ [int(x) for x in input().split()] for _ in range(k) ]

    d  = DSU(n+1)

    for (u,v) in friendEdge:
        d.makeUnion(u,v)
    

    outEdge = dict()
    for (u,v) in enemyEdge+friendEdge:
        if u not in outEdge:
            outEdge[u] = list()
        if v not in outEdge:
            outEdge[v] = list()
        outEdge.get(u).append(v)
        outEdge.get(v).append(u)

    ans = [0] * n
    for i in range(1,n+1):
        ans[i-1] = d.sizeOf(i) - 1
        # print(ans[i-1])
        for v in outEdge.get(i,list()):
            if d.parentOf(i) == d.parentOf(v):
                #print(i,v)
                ans[i-1] -= 1

    # print(ans)
    print(" ".join( map(str,ans) ))

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N, M, K = map(int, input().split())
uf = UnionFind(N)
direct = [set() for _ in range(N)]
IN = sys.stdin.readlines()
for i in range(M):
    a, b = map(int, IN[i].split())
    a -= 1; b -= 1
    uf.union(a, b)
    direct[a].add(b)
    direct[b].add(a)
for i in range(M, M + K):
    a, b = map(int, IN[i].split())
    a -= 1; b -= 1
    if uf.find(a) == uf.find(b):
        direct[a].add(b)
        direct[b].add(a)
ans = []
for i in range(N):
    cnt = -uf.parents[uf.find(i)] - 1
    cnt -= len(direct[i])
    ans.append(cnt)

print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
part_time1 = 0
part_time2 = 0
#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]
    
time_all.append(time.time()-start)

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = [False]*N
label = [0]*N
todo = deque()
num = 0
minus = [0]*N

time_all.append(time.time()-start)
 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1

time_all.append(time.time()-start)
count = 0
for k in range(N):
    time1 = time.time()
    num+=1
    if seen[k] == False:
        H = k
    else:
        continue
    todo += [(H)]
    seen[H] = True
    group = []
    part_time1 += time.time() - time1
    while not len(todo) == 0:
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            count+=1
            if seen[i] == False:
                todo += [i]
                seen[i] = True
#print(count)
time_all.append(time.time()-start)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1
    
time_all.append(time.time()-start)

for i in range(N):
    print(accompany[label[i]] + minus[i]-1)

time_all.append(time.time()-start)

#print(time_all)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [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
        self.parents[y] = x
        self.count[x] +=  self.count[y]
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
part_time1 = 0
part_time2 = 0
#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]
    
time_all.append(time.time()-start)

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = [False]*N
label = [0]*N
todo = deque()
num = 0
minus = [0]*N

time_all.append(time.time()-start)
 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1

time_all.append(time.time()-start)
count = 0
for k in range(N):
    time1 = time.time()
    num+=1
    if seen[k] == False:
        H = k
    else:
        continue
    todo += [(H)]
    seen[H] = True
    group = []
    part_time1 += time.time() - time1
    while not len(todo) == 0:
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            count+=1
            if seen[i] == False:
                todo += [i]
                seen[i] = True
#print(count)
time_all.append(time.time()-start)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1
    
time_all.append(time.time()-start)

print(" ".join(map(lambda x,y : str(accompany[x]+y-1), label, minus)))

time_all.append(time.time()-start)

#print(time_all)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, 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


N, M, K = map(int, input().split())
uf = UnionFind(N)
direct = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    uf.union(a, b)
    direct[a].add(b)
    direct[b].add(a)
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if uf.find(a) == uf.find(b):
        direct[a].add(b)
        direct[b].add(a)
ans = []
for i in range(N):
    cnt = -uf.parents[uf.find(i)] - 1
    cnt -= len(direct[i])
    ans.append(cnt)

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    parent = [-1] * N

    def root(x):
        p, s = parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, parent[p]
        for c in s: parent[c] = x
        return x

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

    def count(x): return -parent[root(x)]

    def unite(x, y):
        xr, yr = root(x), root(y)
        if xr == yr: return
        if parent[xr] > parent[yr]: xr, yr = yr, xr
        parent[xr] += parent[yr]
        parent[yr] = xr

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

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

    print(*[count(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    parent = [-1] * N

    def root(x):
        p, s = parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, parent[p]
        for c in s: parent[c] = x
        return x

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

    def count(x): return -parent[root(x)]

    def unite(x, y):
        xr, yr = root(x), root(y)
        if xr == yr: return
        if parent[xr] > parent[yr]: xr, yr = yr, xr
        parent[xr] += parent[yr]
        parent[yr] = xr

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

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

    print(*[count(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

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

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    ans = [None] * N
    for i in range(N): ans[i] = str(friends_chain.count(i) - friend_or_block[i] - 1)
    print(' '.join(map(str, ans)))

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        p, seq = self.parent[x], list()
        while p >= 0:
            seq.append(x)
            x, p = p, self.parent[p]
        for c in seq: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0 for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(' '.join(map(str, [friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])))

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        p, seq = self.parent[x], list()
        while p >= 0:
            seq.append(x)
            x, p = p, self.parent[p]
        for c in seq: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0 for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(' '.join(map(str, [friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])))

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        p, seq = self.parent[x], list()
        while p >= 0:
            seq.append(x)
            x, p = p, self.parent[p]
        for c in seq: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        if self.count(x) < self.count(y): x, y = y, x
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#Union Find union find

#Root: -1
#child: Parent's ID(non-negative)

class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy:
            return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
cnt = [0] * (n+1)

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

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

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

Submission status: Accepted

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

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        p, seq = self.parent[x], list()
        while p >= 0:
            seq.append(x)
            x, p = p, self.parent[p]
        for c in seq: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        if self.count(x) < self.count(y): x, y = y, x
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

friend_or_block = [0 for _ in range(N)]
friends_chain = UnionFindTree(N)

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if friends_chain.same(c, d):
        friend_or_block[c] += 1
        friend_or_block[d] += 1

print(' '.join(map(str, [friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])))

Submission status: Accepted

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

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        p, seq = self.parent[x], list()
        while p >= 0:
            seq.append(x)
            x, p = p, self.parent[p]
        for c in seq: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        if self.count(x) < self.count(y): x, y = y, x
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

friend_or_block = [set() for _ in range(N)]
friends_chain = UnionFindTree(N)

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    friends_chain.unite(a, b)
    friend_or_block[a].add(b)
    friend_or_block[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if friends_chain.same(c, d):
        friend_or_block[c].add(d)
        friend_or_block[d].add(c)

print(' '.join(map(str, [friends_chain.count(i) - len(friend_or_block[i]) - 1 for i in range(N)])))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        
        # parents が負の時は要素数
        # parents が正の時は親の番号
        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)
 
        # 根が同じ場合はreturn
        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
 
    # xの木の要素数を求める
    def size(self,x):
        return - self.parents[self.find(x)]
 
    # xとyが同じ木なのか確かめる
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
 
n, m, k = (int(x) for x in input().split())

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

for i in range(m):
    a, b = (int(x) for x in input().split())

    a -= 1
    b -= 1

    n_find[a] += 1
    n_find[b] += 1
    uf.union(a, b)

ans = [uf.size(i) -1 - n_find[i] for i in range(n)] 

for i in range(k):
    c, d = (int(x) for x in input().split())

    c -= 1
    d -= 1

    if uf.same(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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

ab = [LI() for _ in range(m)]
cd = [LI() for _ in range(k)]
uf = UnionFind(n)

for a,b in ab:
    uf.union(a-1,b-1)
ans = [uf.size(i)-1 for i in range(n)]
for a,b in ab:
    if uf.same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
for c,d in cd:
    if uf.same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1

print(*ans)

Submission status: Accepted

Solution code:
def make_list(length, loop):
    result = [[] for _ in range(length)]
    for _ in range(loop):
        a, b = map(lambda x: int(x) - 1, input().split())
        result[a].append(b)
        result[b].append(a)
    return result


def main():
    # 敢えてDFSで解いてみる．
    n, m, k = map(int, input().split())
    friend = make_list(n, m)
    brock = make_list(n, k)
    answer = [0] * n
    group_index = [0] * n
    group_id = 1

    def dfs(index):
        q = [index]
        group_index[index] = group_id
        connection = 1
        while not q == []:
            now = q.pop()
            for f in friend[now]:
                if group_index[f] == 0:
                    connection += 1
                    group_index[f] = group_id
                    q.append(f)
        return connection

    id_and_elements = {}
    for i in range(n):
        if group_index[i] == 0:
            id_and_elements[group_id] = dfs(i)
            group_id += 1

    for i in range(n):
        answer[i] += id_and_elements[group_index[i]] - 1
        answer[i] -= len(friend[i])
        for b in brock[i]:
            if group_index[b] == group_index[i]:
                answer[i] -= 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()