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):
class Node():
    def __init__(self, v):
        self.value = v
        self.friends = set()
        self.blocked = set()

n, m, k = list(map(int, input().split()))
link = {i: Node(i) for i in range(1, n+1)}
groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a].friends.add(b)
    link[b].friends.add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c].blocked.add(d)
    link[d].blocked.add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i].blocked - link[i].friends) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")


class Node():
    def __init__(self, v):
        self.value = v
        self.friends = set()
        self.blocked = set()

n, m, k = list(map(int, input().split()))
link = {i: Node(i) for i in range(1, n+1)}
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a].friends.add(link[b])
    link[b].friends.add(link[a])

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c].blocked.add(link[d])
    link[d].blocked.add(link[c])

def traverse(hist, friends, blocked):
    for f in friends:
        if f not in hist:
            if f not in blocked:
                hist.add(f)
            traverse(hist, f.friends, blocked)
    return hist

for i in range(1, n+1):
    node = link[i]
    hist = traverse(set(), node.friends, node.blocked)
    cnt = len(hist - set([node]) - node.friends - node.blocked)
    print(cnt, end="" if i == n else " ")


n, m, k = list(map(int, input().split()))
link = {i: (set(), set()) for i in range(1, n+1)}

friends = 0
blocked = 1

groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a][friends].add(b)
    link[b][friends].add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c][blocked].add(d)
    link[d][blocked].add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i][blocked] - link[i][friends]) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")


class Tree:
    def __init__(self, v: int):
        self.value = v
        self.size = 1
        self.depth = 1
        self.parent = None
        self.friends = set()
        self.blocked = 0

    def get_root(self):
        t = self
        while(t.parent != None):
            t = t.parent
        return t

    def merge(self, t):
        p, c = (self, t) if self.depth > t.depth else (t, self)
        c.parent = p
        p.depth = max(p.size, c.size + 1)
        p.size += c.size

def main():
    n, m, k = [int(s) for s in input().split()]
    forest = [Tree(i+1) for i in range(n)]

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        ta, tb = forest[a-1], forest[b-1]
        ta.friends.add(b)
        tb.friends.add(a)
        ra = ta.get_root()
        rb = tb.get_root()
        if ra != rb:
            ra.merge(rb)

    roots = [t.get_root() for t in forest]
    for i in range(k):
        c, d = [int(s) for s in input().split()]
        tc, td = forest[c-1], forest[d-1]
        rc = roots[c-1]
        rd = roots[d-1]
        if rc == rd:
            tc.blocked +=1
            td.blocked +=1

    cands = []
    for t in forest:
        root = roots[t.value - 1]
        cand = root.size - len(t.friends) - t.blocked - 1
        cands.append(str(cand))
    print(" ".join(cands))

if __name__ == '__main__':
    main()


Verdicts: Time Limit Exceeded

Runtime Error

Time Limit Exceeded

Accepted