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 = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] 
friend = [[] for _ in range(n)]
friend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

num = 0
while(num < n):
    #print(num)
    for x in friend[num]:
        friend_line[x]=friend_line[num]
    num+=1
    #print(frend_line)

for _ in range(k):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

#print(friend)
#print(friend_line)

for i in range(n):
    print(friend_line.count(friend_line[i])-1-len(friend[i]),end=" ")

n,m,k = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] 
frend = [[] for _ in range(n)]
group = [[] for _ in range(n)]
frend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    frend[a-1].append(b-1)
    frend[b-1].append(a-1)
for _ in range(k):
    a,b= list(map(int,input().split()))
    group[a-1].append(b-1)
    group[b-1].append(a-1)
#print(frend)
num = 0
while(num < n):
    #print(num)
    for x in frend[num]:
        frend_line[x]=frend_line[num]
    num+=1
    #print(frend_line)

#print(frend_line)
for i in range(n):
    for j in range(i+1,n):
        if not j in frend[i] and not j in group[i] and frend_line[i]==frend_line[j]:
            ans_l[i]+=1
            ans_l[j]+=1

for ans in ans_l:
    print(ans,end=" ")
print()

n,m,k = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] 
friend = [[] for _ in range(n)]
friend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

num = 0
while(num < n):
    #print(num)
    for x in friend[num]:
        friend_line[x]=friend_line[num]
    num+=1
    #print(frend_line)

for _ in range(k):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

print(friend)
print(friend_line)

for i in range(n):
    print(friend_line.count(friend_line[i])-1-len(friend[i]),end=" ")

import sys
import math
from collections import deque
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        
        return -self.parents[self.find(x)]

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

    def members(self, x):
        
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        
        return len(self.roots())

    def all_group_members(self):
        
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    

def main():
    n, m, k = list(map(int,sys.stdin.readline().split()))
    uf = UnionFind(n)
    num_of_friends = [-1] * n

    for _ in range(m):
        a, b = list(map(int,sys.stdin.readline().split()))
        a -= 1
        b -= 1
        uf.union(a,b)
        num_of_friends[a] -= 1
        num_of_friends[b] -= 1
        #print(num_of_friends)
    
    """
    for i2 in range(n):
        roots[find(i2)] += 1
        print(roots)"""
    for i3 in range(n):
        num_of_friends[i3] += uf.size(i3)
        #print(num_of_friends)

    for _ in range(k):
        c, d = list(map(int,sys.stdin.readline().split()))
        c -= 1
        d -= 1
        """
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1
        """
        if uf.same(c,d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1    
    #print(num_of_friends)
    print(' '.join([str(number) for number in num_of_friends]))

if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted