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 sys import stdin
import sys
sys.setrecursionlimit(20000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,i)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
import sys
sys.setrecursionlimit(2000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    # friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        # if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            candidate.add(friend)
            count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
import sys
sys.setrecursionlimit(2000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            # friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[[None,None] for i in range(N+1)]
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    cnt[0]+=1
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    cnt=[0]
    color =set()
    if counter[i][0] is None:
        friend_tansaku(i,i)
        cnt=cnt[0]
        for aa in color:
            counter[aa]=[color,cnt]
    color,cnt =counter[i][0],counter[i][1]
    for k in block_list[i]:
        if k not in color:
            cnt+=1

    count=cnt-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted