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
import time

N, M, K = [int(i) for i in input().split(" ")]

friend_dict = defaultdict(lambda:[])
block_dict = defaultdict(lambda:[])
root = {}
numroot = {}
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    ab = a
    bb = b

    a = min(ab, bb)
    b = max(ab, bb)
    #print((a, b))

    for x, y in ((a, b), (b, a)):
        friend_dict[x].append(y)

    if b in root:
        root[a] = b
    else:
        root[b] = a

#print(root)

union = dict(zip(range(N), range(N)))
unionnum = defaultdict(lambda:1)
for before, rootnum in root.items():
    while rootnum in root:
        rootnum = root[rootnum]
    union[before] = rootnum
    unionnum[rootnum] += 1

#print(union)


time.sleep(1)

result = []
for i in range(N):
    ret = unionnum[union[i]] -1

    #print(f"un={ret}")

    for friend in friend_dict[i]:
        if union[friend] == union[i]:
            ret -=1
    for block in block_dict[i]:
        if union[block] == union[i]:
            ret -=1
    result.append(ret)


#print(union)
print(" ".join([str(i) for i in result]))


N, M, K = [int(i) for i in input().split(" ")]

friend_list = []
block_list = []
root = {}
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    ab = a
    bb = b

    a = min(ab, bb)
    b = max(ab, bb)
    print((a, b))

    friend_list.append((a, b))
    if b in root:
        root[a] = root[b]
    else:
        root[b] = a

union = []
for i in range(N):
    c_root = i
    while True:
        if c_root in root:
            c_root = root[c_root]
        else:
            union.append(c_root)
            break


for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    block_list.append((a, b))


result = []
for i in range(N):
    ret = 0
    if union[i] is None:
        result.append(0)
        continue
    for j in range(N):
        if i == j:
            continue
        if union[i] != union[j]:
            continue
        if (i, j) in block_list:
            continue
        if (j, i) in block_list:
            continue
        if (i, j) in friend_list:
            continue
        if (j, i) in friend_list:
            continue
        ret += 1
    result.append(ret)

#print(union)
print(" ".join([str(i) for i in result]))

from collections import defaultdict
import time

N, M, K = [int(i) for i in input().split(" ")]

friend_dict = defaultdict(lambda:[])
block_dict = defaultdict(lambda:[])
root = {}
numroot = {}
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    ab = a
    bb = b

    a = min(ab, bb)
    b = max(ab, bb)
    #print((a, b))

    for x, y in ((a, b), (b, a)):
        friend_dict[x].append(y)

    if b in root:
        root[a] = b
    else:
        root[b] = a

#print(root)

union = dict(zip(range(N), range(N)))
unionnum = defaultdict(lambda:1)
for before, rootnum in root.items():
    while rootnum in root:
        rootnum = root[rootnum]
    union[before] = rootnum
    unionnum[rootnum] += 1

#print(union)


time.sleep(1)

result = []
for i in range(N):
    ret = unionnum[union[i]] -1

    #print(f"un={ret}")

    for friend in friend_dict[i]:
        if union[friend] == union[i]:
            ret -=1
    for block in block_dict[i]:
        if union[block] == union[i]:
            ret -=1
    result.append(ret)


#print(union)
print(" ".join([str(i) for i in result]))


N, M, K = [int(i) for i in input().split(" ")]

friend_list = []
block_list = []
root = {}
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    ab = a
    bb = b

    a = min(ab, bb)
    b = max(ab, bb)
    print((a, b))

    friend_list.append((a, b))
    if b in root:
        root[a] = root[b]
    root[b] = a

print(root)

union = []
for i in range(N):
    c_root = i
    while True:
        if c_root in root:
            c_root = root[c_root]
        else:
            union.append(c_root)
            break


for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    block_list.append((a, b))


result = []
for i in range(N):
    ret = 0
    if union[i] is None:
        result.append(0)
        continue
    for j in range(N):
        if i == j:
            continue
        if union[i] != union[j]:
            continue
        if (i, j) in block_list:
            continue
        if (j, i) in block_list:
            continue
        if (i, j) in friend_list:
            continue
        if (j, i) in friend_list:
            continue
        ret += 1
    result.append(ret)

print(root)
print(union)
print(" ".join([str(i) for i in result]))


N, M, K = [int(i) for i in input().split(" ")]

friend_list = []
block_list = []
root = {}
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    ab = a
    bb = b

    a = min(ab, bb)
    b = max(ab, bb)
    print((a, b))

    friend_list.append((a, b))
    if b in root:
        root[a] = root[b]
    else:
        root[b] = a

union = []
for i in range(N):
    c_root = i
    while True:
        if c_root in root:
            c_root = root[c_root]
        else:
            union.append(c_root)
            break


for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    block_list.append((a, b))


result = []
for i in range(N):
    ret = 0
    if union[i] is None:
        result.append(0)
        continue
    for j in range(N):
        if i == j:
            continue
        if union[i] != union[j]:
            continue
        if (i, j) in block_list:
            continue
        if (j, i) in block_list:
            continue
        if (i, j) in friend_list:
            continue
        if (j, i) in friend_list:
            continue
        ret += 1
    result.append(ret)

#print(union)
print(" ".join([str(i) for i in result]))

from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.volume > taroot.volume:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)


#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted