Problem: 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?

Submission attempts (in order):
# -*- coding: utf-8 -*-

#def find_friend(tree_node, target):
#    for friend in tree_node.friends:
#        if target in friend.friend_numbers:
#            return True
#
#    flags = []
#    for friend in tree_node.friends:
#        flags.append(find_friend(friend, target))
#    if True in flags:
#        return True
#    return False

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))

def find_friend(root, target):
    queue = [root]
    already_list = [root.val]
    while len(queue) > 0:
        node = queue.pop(0)
        if target in node.friend_numbers:
            return True
        
        for friend in node.friends:
            if friend.val not in already_list:
                queue.append(friend)
                already_list.append(friend.val)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate = []

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

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

for k, v in tree_nodes.items():
    display(v)

candidates = []
for k, v in tree_nodes.items():
    
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        
        flag = find_friend(v, n)
        if flag:
            candidate += 1
        print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

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

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

# -*- 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]

[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) + ' '

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

Verdicts: Wrong Answer

Accepted