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):
# ABC157d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    

    class UnionFind:
        def __init__(self, n):
            self.tree = [i for i in range(n)]
            self.member = [1]*n

        def root(self, x):
            if(self.tree[x] == x):
                return x
            self.tree[x] = self.root(self.tree[x])
            return self.tree[x]  

        def same(self, x, y):  
            return self.root(x) == self.root(y)

        def unite(self, x, y):
            x = self.root(x)
            y = self.root(y)
            if(x == y):
                return
            new = self.member[x]+self.member[y]
            self.member[x] = new
            self.member[y] = new
            self.tree[x] = y

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

    friend = [set() for i in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        friend[a - 1].add(b - 1)
        friend[b - 1].add(a - 1)
        tree.unite(a-1, b-1)
    block = [set() for i in range(n)]
    for _ in range(k):
        c, e = map(int, input().split())
        if tree.same(c - 1, e - 1):
            block[c - 1].add(e - 1)
            block[e - 1].add(c - 1)
    ans = []
    for i in range(n):
        print(i, tree.member[tree.root(i)], len(friend[i]), len(block[i]))
        ans.append(tree.member[tree.root(i)]-len(friend[i])-len(block[i])-1)
    print(*ans)


if __name__ == '__main__':
    main()


# ABC157d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    

    class UnionFind:
        def __init__(self, n):
            self.tree = [i for i in range(n)]
            self.member = [1]*n

        def root(self, x):
            if(self.tree[x] == x):
                return x
            self.tree[x] = self.root(self.tree[x])
            return self.tree[x]  

        def same(self, x, y):  
            return self.root(x) == self.root(y)

        def unite(self, x, y):
            x = self.root(x)
            y = self.root(y)
            if(x == y):
                return
            new = self.member[x]+self.member[y]
            self.member[x] = new
            self.member[y] = new
            self.tree[x] = y

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

    friend = [set() for i in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        friend[a - 1].add(b - 1)
        friend[b - 1].add(a - 1)
        tree.unite(a-1, b-1)
    block = [set() for i in range(n)]
    for _ in range(k):
        c, e = map(int, input().split())
        if tree.same(c - 1, e - 1):
            block[c - 1].add(e - 1)
            block[e - 1].add(c - 1)
    ans = []
    for i in range(n):
        
        ans.append(tree.member[tree.root(i)]-len(friend[i])-len(block[i])-1)
    print(*ans)


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted