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 defaultdict

n, m, k = map(int, input().split())
friend = defaultdict(list)
block = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    friend[a].append(b)
for i in range(k):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    block[a].append(b)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    for j in friend[i]:
        for k in friend[k]:
            if k not in friend[i] and k not in block[i]:
                res[i - 1] += 1
for i in range(n):
    print(res[i], sep = " ")

from collections import defaultdict

n, m, k = map(int, input().split())
friend = defaultdict(list)
block = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    friend[a].append(b)
for i in range(k):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    block[a].append(b)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    for j in friend[i]:
        for k in friend[j]:
            if k not in friend[i] and k not in block[i]:
                res[i - 1] += 1
                res[k-1] += 1
for i in range(n):
    print(res[i],end = " ")

from collections import defaultdict
n, m, k = map(int, input().split())
friend = defaultdict(set)
block = defaultdict(set)
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    queue = list(friend[i])
    while queue:
        j = queue.pop(0)
        for k in friend[j]:
            if k != i and k not in friend[i] and k not in block[i]:
                res[i-1] += 1
                friend[i].add(k)
                queue.append(k)
                if i not in friend[k]:
                    res[k-1] += 1
                    friend[k].add(i)
for i in range(n):
    print(res[i], end=" ")

from collections import deque
n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
stack = deque()
ans = [0]*(n+1)
visited = [0]*(n+1)
for i in range(1, n+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in friend[n]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & friend[i]) - len(link & block[i]) -1
print(*ans[1:])

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted