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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def dfs(v, seen, overall, connected_components):
    seen[v] = True
    connected_components.add(v)
    for nv in overall[v]:
        if seen[nv] == True:continue
        dfs(nv, seen, overall, connected_components)
def main():
    N, M, K = map(int, input().split())
    overall = {}
    friends = {}
    blocks = {}
    for i in range(N):
        overall[i] = set()
        friends[i] = set()
        blocks[i] = set()
    for _ in range(M):
        a, b = map(int, input().split())
        overall[a-1].add(b-1)
        overall[b-1].add(a-1)
        friends[a-1].add(b-1)
        friends[b-1].add(a-1)
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c-1].add(d-1)
        blocks[d-1].add(c-1)
    ans = {}
    seen = [False] * N
    for i in range(N):
        if seen[i] == True:continue
        connected_components = set()
        dfs(i, seen, overall, connected_components)
        for v in list(connected_components):
            ans[v] = connected_components - {v}
    for i in range(N):
        print(len(ans[i]-friends[i]-blocks[i]), end=" ")
if __name__ == "__main__":
    main()

import sys
sys.setrecursionlimit(2147483647)
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
connected_components = []
count = 0
counts = [0 for _ in range(N)]
seen = [False for _ in range(N)]
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)
def dfs_connected(v, order):
    seen[v] = True

import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends = {i: set() for i in range(N)}
blocks = {i: set() for i in range(N)}

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

for _ in range(K):
    a, b = map(int, input().split())
    blocks[a-1].add(b-1)
    blocks[b-1].add(a-1)

counts = [0] * N
seen = [False] * N
def dfs(v):
    if seen[v] == True:
        return
    seen[v] = True
    for node in friends[v]:
        c.add(node)
        dfs(node)
 
for v in range(N):
    if seen[v] == True:
        continue
    c = set()
    dfs(v)
    l = len(c)
    for i in c:
        counts[i] = l - 1
        counts[i] -= len(c & friends[i])
        counts[i] -= len(c & blocks[i])
print(' '.join(map(str, counts)))

Verdicts: Time Limit Exceeded

Wrong Answer

Accepted