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):
n, m, k = map(int, input().split())

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = []
nseen = {i for i in range(1, n+1)}
while len(nseen)>0:
    stack = [nseen.pop()]
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        for c_node in friends[node]:
            if c_node not in nseen:
                continue
            stack.append(c_node)
            nseen.remove(c_node)
    groups.append(tmp)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

n, m, k = map(int, input().split())

friends = []
blocks = []
groups = []
fs = [[] for _ in range(n+1)]
bs = [[] for _ in range(n+1)]

for _ in range(m):
    friends.append(tuple(map(int, input().split())))
for _ in range(k):
    blocks.append(tuple(map(int, input().split())))

for i, j in friends:
    fs[i].append(j)
    fs[j].append(i)

for i, j in blocks:
    bs[i].append(j)
    bs[j].append(i)

def search_groups(x, y):
    xx = -1
    yy = -1
    for ind, i in enumerate(groups):
        if x in i:
            xx = ind
            if yy >= 0:
                break
        if y in i:
            yy = ind
            if xx >= 0:
                break
    return xx, yy

for i, j in friends:
    ii, jj = search_groups(i, j)
    if ii==jj==-1:
        groups.append({i, j})
    elif ii==-1:
        groups[jj].add(i)
    elif jj==-1:
        groups[ii].add(j)
    elif ii!=jj:
        rm1 = groups[ii]
        rm2 = groups[jj]
        groups.append(rm1|rm2)
        groups.remove(rm1)
        groups.remove(rm2)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(fs[i]) - set(bs[i]))-1, end=' ')
            break

n, m, k = map(int, input().split())

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = []
nseen = {i for i in range(1, n+1)}
while len(nseen)>0:
    stack = [nseen.pop()]
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        nseen.remove(node)
        for c_node in friends[node]:
            if c_node not in nseen:
                continue
            stack.append(c_node)
    groups.append(tmp)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

n, m, k = map(int, input().split())

friends = []
blocks = []
groups = []
fs = [[] for _ in range(n+1)]
bs = [[] for _ in range(n+1)]

for _ in range(m):
    friends.append(tuple(map(int, input().split())))
for _ in range(k):
    blocks.append(tuple(map(int, input().split())))

for i, j in friends:
    fs[i].append(j)
    fs[j].append(i)

for i, j in blocks:
    bs[i].append(j)
    bs[j].append(i)

seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in fs[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(fs[i]) - set(bs[i]))-1, end=' ')
            break

n, m, k = map(int, input().split())

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = []
seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in friends[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

from collections import deque
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    blocks[c-1].append(d-1)
    blocks[d-1].append(c-1)


grp_idx = [-1]*n
grp_szs = []
grp = 0
for i in range(n):
    if grp_idx[i]>=0:
        continue
    queue = deque([i])
    grp_idx[i] = grp
    tmp = 0
    while len(queue)>0:
        node = queue.popleft()
        for c_node in friends[node]:
            if grp_idx[c_node]>=0:
                continue
            grp_idx[c_node] = grp
            tmp += 1
            queue.append(c_node)
    grp_szs.append(tmp)
    grp += 1
ans = []
for i in range(n):
    tmp = grp_szs[grp_idx[i]]
    for j in friends[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    for j in blocks[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    ans.append(tmp)
print(*ans)

Verdicts: Time Limit Exceeded

Wrong Answer

Runtime Error

Time Limit Exceeded

Time Limit Exceeded

Accepted