UnionFind Tree is the standard, but beginners should first master DFS. Do not use recursive functions for simple operations.
reference ABC 157 D Gentle explanation of the problem
Sample code
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
#Adjacency list of friends
for _ in range(M):
a, b = map(int, input().split())
a, b = a - 1, b - 1
F[a].append(b)
F[b].append(a)
#Adjacency list of blocks
for _ in range(K):
c, d = map(int, input().split())
c, d = c - 1, d - 1
B[c].append(d)
B[d].append(c)
#Friendship group (dictionary type)
D = {}
#Group parent
parent = [-1] * N
#Visit management
visited = [False] * N
for root in range(N):
if visited[root]:
continue
D[root] = set([root])
#Visited stack
stack = [root]
#Until there are no more places to visit
while stack:
#Pop up visitors
n = stack.pop()
#Visited visitor
visited[n] = True
#Set parents for a group of visitors
parent[n] = root
#Add root friends to groups and destinations
for to in F[n]:
if visited[to]:
continue
D[root].add(to)
stack.append(to)
ans = [0] * N
for iam in range(N):
#Set up your own friendship group
group = D[parent[iam]]
#Remove friends and yourself from the group
tmp_ans = len(group) - len(F[iam]) - 1
#Remove blocks from group
for block in B[iam]:
if block in group:
tmp_ans -= 1
ans[iam] = tmp_ans
print(*ans, sep=' ')
Recommended Posts