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 UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*n
    self.rank = [0]*n
    
  def find_root(self, e):
    if self.root[e] < 0:
      return e
    else:
      r = self.find_root(self.root[e])
      self.root[e] = r
      return r
    
  def combine(self, e1, e2):
    root1 = self.find_root(e1)
    root2 = self.find_root(e2)
    if root1 == root2:
      pass
    elif self.rank[root1] < self.rank[root2]:
      self.root[root1] += self.root[root2]
      self.root[root2] = root1
      self.rank[root1] = self.rank[root2] + 1
    elif self.rank[root2] < self.rank[root1]:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] = self.rank[root1] + 1
    else:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] += 1
      
  def in_the_same_group(self, e1, e2):
      r1 = self.find_root(e1)
      r2 = self.find_root(e2)
      if r1 == r2:
        return True
      return False
  

NMK = input().split()
N = int(NMK[0])
M = int(NMK[1])
K = int(NMK[2])
uf = UnionFind(N)
from collections import defaultdict

friend_list = [0]*n
for _ in range(M):
  AB = input().split()
  A = int(AB[0])-1
  B = int(AB[1])-1
  uf.combine(A,B)
  friend_list[A] += 1
  friend_list[B] += 1

block_list = [0]*n
for _ in range(K):
  CD = input().split()
  C = int(CD[0])-1
  D = int(CD[1])-1
  if uf.in_the_same_group(C, D):
    block_list[C] += 1
    block_list[D] += 1

cnt = defaultdict(int)
ans = []
for i in range(N):
  cnt[i] = -uf.root[uf.find_root(i)] - 1 - friend_list[i] - block_list[i]
  ans.append(str(cnt[i]))

print(" ".join(ans))

from collections import defaultdict

friend_list = defaultdict(int)
for _ in range(M):
  AB = input().split()
  A = int(AB[0])-1
  B = int(AB[1])-1
  uf.combine(A,B)
  friend_list[A] += 1
  friend_list[B] += 1

block_list = defaultdict(int)
for _ in range(K):
  CD = input().split()
  C = int(CD[0])-1
  D = int(CD[1])-1
  if uf.in_the_same_group(C, D):
    block_list[C] += 1
    block_list[D] += 1

cnt = defaultdict(int)
ans = []
for i in range(N):
  cnt[i] = -uf.root[uf.find_root(i)] - 1 - friend_list[i] - block_list[i]
  ans.append(str(cnt[i]))

print(" ".join(ans))

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*n
    self.rank = [0]*n
    
  def find_root(self, e):
    if self.root[e] < 0:
      return e
    else:
      r = self.find_root(self.root[e])
      self.root[e] = r
      return r
    
  def combine(self, e1, e2):
    root1 = self.find_root(e1)
    root2 = self.find_root(e2)
    if root1 == root2:
      pass
    elif self.rank[root1] < self.rank[root2]:
      self.root[root1] += self.root[root2]
      self.root[root2] = root1
      self.rank[root1] = self.rank[root2] + 1
    elif self.rank[root2] < self.rank[root1]:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] = self.rank[root1] + 1
    else:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] += 1
      
  def in_the_same_group(self, e1, e2):
      r1 = self.find_root(e1)
      r2 = self.find_root(e2)
      if r1 == r2:
        return True
      return False
  

NMK = input().split()
N = int(NMK[0])
M = int(NMK[1])
K = int(NMK[2])
uf = UnionFind(N)
from collections import defaultdict
friend_list = [0]*N
for _ in range(M):
  AB = input().split()
  A = int(AB[0])-1
  B = int(AB[1])-1
  uf.combine(A,B)
  friend_list[A] += 1
  friend_list[B] += 1

block_list = [0]*N
for _ in range(K):
  CD = input().split()
  C = int(CD[0])-1
  D = int(CD[1])-1
  if uf.in_the_same_group(C, D):
    block_list[C] += 1
    block_list[D] += 1

block_list*n
cnt = defaultdict(int)
ans = []
for i in range(N):
  cnt[i] = -uf.root[uf.find_root(i)] - 1 - friend_list[i] - block_list[i]
  ans.append(str(cnt[i]))

print(" ".join(ans))

class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) 
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] 
print(*ans[1:])


Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted