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):
from collections import deque
import sys
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_matrix = [[0] * N for _ in range(N)]
block_matrix = [[0] * N for _ in range(N)]

num_frineds = [0] * N
num_blocks = [0] * N

for _ in range(M):
    A, B = map(int, input().split())
    friend_matrix[A-1][B-1] = 1
    friend_matrix[B-1][A-1] = 1
    num_frineds[A-1] += 1
    num_frineds[B-1] += 1

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

if DEBUG:
    # print("friend_matrix: {}".format(friend_matrix))
    print("friend_matrix:")
    for row in friend_matrix:
        print(row)
    # print("block_matrix: {}".format(block_matrix))
    print("block_matrix:")
    for row in block_matrix:
        print(row)
    print("enter!!")

count = 0
labels = [-1] * N
graph_sizes = []
for n in range(N):
    size = 0
    if labels[n-1] == -1:
        queue = deque([n])
        while queue:
            node = queue.popleft()
            if labels[node-1] == -1:
                labels[node-1] = count
                size += 1
            else:
                continue
            for i in range(N):
                if labels[i-1] == -1 and friend_matrix[node-1][i-1] == 1:
                    queue.append(i)
        count += 1
        graph_sizes.append(size)
print(num_blocks)
if DEBUG:
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

frind_candidate = [0] * N
for n in range(N):
    # num_block = sum(block_matrix[n])
    num_block = 0
    for i in range(N):
        if block_matrix[n][i] == 1 and labels[n] == labels[i]:
            num_block += 1
    # num_frined = sum(friend_matrix[n])
    num_frined = num_frineds[n]
    if not DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    frind_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1
frind_candidate = list(map(str, frind_candidate))
print(" ".join(frind_candidate))


from collections import deque
import sys
import time
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_matrix = [[0] * N for _ in range(N)]
block_matrix = [[0] * N for _ in range(N)]

num_connected_friends = [0] * N
num_connected_blocks = [0] * N

for _ in range(M):
    A, B = map(int, input().split())
    friend_matrix[A-1][B-1] = 1
    friend_matrix[B-1][A-1] = 1
    num_connected_friends[A-1] += 1
    num_connected_friends[B-1] += 1

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

if DEBUG:
    # print("friend_matrix: {}".format(friend_matrix))
    print("friend_matrix:")
    for row in friend_matrix:
        print(row)
    # print("block_matrix: {}".format(block_matrix))
    print("block_matrix:")
    for row in block_matrix:
        print(row)
    print("enter!!")

count = 0
labels = [-1] * N
graph_sizes = []
total_iteration = 0
for n in range(N):
    if DEBUG:
        print("root_node: {}, count: {}".format(n+1, count))
    if labels[n-1] == -1:
        queue = deque([n+1])
        labels[n] = count
        size = 0
        while queue:
            total_iteration += 1
            if DEBUG:
                print("queue:{}".format(queue))
            node = queue.popleft()
            size += 1
            if DEBUG:
                print("node:{}".format(node))
            for i in range(N):
                if labels[i] == -1 and friend_matrix[node-1][i] == 1:
                    labels[i] = count
                    queue.append(i+1)
                if labels[node-1] == labels[i]:
                    num_connected_blocks[node-1] += block_matrix[node-1][i]
            if DEBUG:
                print("labels: {}".format(labels))
            # time.sleep(0.2)
        count += 1
        graph_sizes.append(size)
if DEBUG:
    print("total_iteration: {}".format(total_iteration))
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))
    print("num_connected_friends: {}".format(num_connected_friends))
    print("num_connected_blocks: {}".format(num_connected_blocks))

frind_candidate = [0] * N
for n in range(N):
    # num_block = sum(block_matrix[n])
    # num_block = 0
    
    #     if block_matrix[n][i] == 1 and labels[n] == labels[i]:
    #         num_block += 1
    num_block = num_connected_blocks[n]
    # num_frined = sum(friend_matrix[n])
    num_frined = num_connected_friends[n]
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    frind_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1
frind_candidate = list(map(str, frind_candidate))
# print(" ".join(frind_candidate))
print(*frind_candidate)


from collections import deque
import sys
import time
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_relations = [[] for _ in range(N+1)]
block_relations = [[] for _ in range(N+1)]

num_connected_friends = [0] * (N+1)
num_connected_blocks = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    friend_relations[A].append(B)
    friend_relations[B].append(A)

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

if DEBUG:
    print("friend_relations:")
    for i, row in enumerate(friend_relations):
        print("node: {}, relation: {}".format(i, row))
    print("block_matrix:")
    for i, row in enumerate(block_relations):
        print("node: {}, relation: {}".format(i, row))

count = 0
labels = [-1] * (N+1)
graph_sizes = []
total_iteration = 0
for n in range(1, N+1):
    if DEBUG:
        print("root_node: {}, count: {}".format(n, count))
    if labels[n] == -1:
        queue = deque([n])
        labels[n] = count
        size = 0
        while queue:
            if DEBUG:
                print("queue:{}".format(queue))
            node = queue.popleft()
            size += 1
            if DEBUG:
                print("node:{}".format(node))
            for next_node in friend_relations[node]:
                total_iteration += 1
                if labels[next_node] == -1:
                    labels[next_node] = count
                    queue.append(next_node)
            if DEBUG:
                print("labels: {}".format(labels))
            # time.sleep(0.2)
        count += 1
        graph_sizes.append(size)
if DEBUG:
    print("total_iteration: {}".format(total_iteration))
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

friend_candidate = [0] * (N+1)
for n in range(1, N+1):
    num_block = sum([1 for i in block_relations[n] if labels[n] == labels[i]])
    num_frined = len(friend_relations[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    friend_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1

print(*friend_candidate)


from collections import deque
import sys
import time
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_relations = [[] for _ in range(N+1)]
block_relations = [[] for _ in range(N+1)]

num_connected_friends = [0] * (N+1)
num_connected_blocks = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    friend_relations[A].append(B)
    friend_relations[B].append(A)

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

if DEBUG:
    print("friend_relations:")
    for i, row in enumerate(friend_relations):
        print("node: {}, relation: {}".format(i, row))
    print("block_matrix:")
    for i, row in enumerate(block_relations):
        print("node: {}, relation: {}".format(i, row))

count = 0
labels = [-1] * (N+1)
graph_sizes = []
total_iteration = 0
for n in range(1, N+1):
    if DEBUG:
        print("root_node: {}, count: {}".format(n, count))
    if labels[n] == -1:
        queue = deque([n])
        labels[n] = count
        size = 0
        while queue:
            if DEBUG:
                print("queue:{}".format(queue))
            node = queue.popleft()
            size += 1
            if DEBUG:
                print("node:{}".format(node))
            for next_node in friend_relations[node]:
                total_iteration += 1
                if labels[next_node] == -1:
                    labels[next_node] = count
                    queue.append(next_node)
            if DEBUG:
                print("labels: {}".format(labels))
            # time.sleep(0.2)
        count += 1
        graph_sizes.append(size)
if DEBUG:
    print("total_iteration: {}".format(total_iteration))
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

friend_candidate = [0] * (N+1)
for n in range(1, N+1):
    num_block = sum([1 for i in block_relations[n] if labels[n] == labels[i]])
    num_frined = len(friend_relations[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    friend_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1

print(*friend_candidate[1:])


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted