Problem:


Score : 400 points

Problem Statement

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?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
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):	#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())


n,m,k = map(int,input().split())
suggest = UnionFind(n)
follow = [0]*n
block = [0]*n
for i in range(n):
    follow[i] = list()
    block[i]  = list()
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    suggest.union(a,b)
    follow[a].append(b)
    follow[b].append(a)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    block[c].append(d)
    block[d].append(c)
ans = ""
suggestfriend = [0]*n
ans = ""
for i in range(n):
    blockperson = 0
    union = suggest.size(i)
    for j in range(len(block[i])):
        if(suggest.same(i,block[i][j])):
            blockperson += 1
    ans += str(union - blockperson -len(follow[i]) - 1) + " "
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,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)]


N,M,K=map(int,input().split())
uf=UnionFind(N+1)
friends={x:set() for x in range(1,N+1)}
blocks={x:set() for x in range(1,N+1)}
ans=[N-1]*(N+1)

for _ in range(M):
  A,B=map(int,input().split())
  friends[A].add(B)
  friends[B].add(A)
  uf.union(A,B)

for _ in range(K):
  C,D=map(int,input().split())
  if uf.find(C)==uf.find(D):
    blocks[C].add(D)
    blocks[D].add(C)

for i in range(1,N+1):
  if uf.size(i)==-1:
    print(0)
    continue
  print(abs(uf.size(i))-len(friends[i])-len(blocks[i])-1,end=' ')

Submission status: Accepted

Solution code:
class Union_Find:
  def __init__(self,n=0):
    self.vertices=n
    self.mother=[-1 for i in range(self.vertices)]
    self.size_temp=[1 for i in range(self.vertices)]
  
  def root(self,x):
    normalize_v=[]
    while x!=-1:
      normalize_v.append(x)
      y=x
      x=self.mother[x]
    for i in normalize_v[:-1]:
      self.mother[i]=y
    return y
  
  def union(self,x,y):
    root_x=self.root(x)
    root_y=self.root(y)
    if root_x!=root_y:
      self.mother[root_x]=root_y
      self.size_temp[root_y]+=self.size_temp[root_x]
  
  def find(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False
  
  def size(self,x):
    return self.size_temp[self.root(x)]



n,m,k=map(int,input().split())
uf=Union_Find(n)
friend=[0 for i in range(n)]
block=[[] for i in range(n)]

for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  friend[a]+=1
  friend[b]+=1
  uf.union(a,b)

for i in range(k):
  a,b=map(lambda x:int(x)-1,input().split())
  block[a].append(b)
  block[b].append(a)

r=""
for i in range(n):
  size=uf.size(i)
  size-=friend[i]
  for j in block[i]:
    if uf.find(i,j):
      size-=1
  r+=str(size-1)+" "
print(r[:-1])

Submission status: Accepted

Solution code:
class DisjointSets:#Union-Find
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]
    def unite(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]

n, m, k = map(int, input().split())
ds = DisjointSets(n)
friends_count = [0] * n

for _ in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    friends_count[a] += 1
    friends_count[b] += 1
    ds.unite(a, b)
block_count = [0] * n
for _ in range(k):
    a, b = map(lambda x:int(x)-1, input().split())
    if ds.find(a) == ds.find(b):
        block_count[a] += 1
        block_count[b] += 1

print(' '.join([str(ds.size(i) - friends_count[i] - block_count[i] - 1) for i in range(n)]))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x); y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def group_size(self, x):
        return self.size[self.find(x)]
n, m, k = map(int, input().split())
a = [0]*m; b = [0]*m; c = [0]*k; d = [0]*k; x = [0]*n
direct = [[] for _ in range(n)]; uf = UnionFind(n)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1; b[i] -= 1
    direct[a[i]].append(b[i]); direct[b[i]].append(a[i])
    uf.unite(a[i], b[i])
for i in range(k):
    c[i], d[i] = map(int, input().split())
    c[i] -= 1; d[i] -= 1
    if uf.is_same(c[i], d[i]):
        direct[c[i]].append(d[i]); direct[d[i]].append(c[i])
for i in range(n): x[i] = uf.group_size(i)-len(direct[i])-1
print(*x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        flag[i] = group
        while len(deque) > 0:
            target = deque.popleft()
            flag[target] = group
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                flag[frend] = group
                deque.append(frend)
        group += 1

    groups = [[] for i in range(N)]
    for i in range(len(flag)):
        groups[flag[i]].append(i)
    ans = []
    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        candidate = len(groups[i_group]) - len(friends[i]) - 1
        for blocking in blocks[i]:
            if blocking in groups[i_group]:
                candidate -= 1
        ans.append(candidate)
    print(" ".join(map(str, ans)))


main()

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
friendships = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  friendships[a-1].append(b-1)
  friendships[b-1].append(a-1)
blockships = [[] for _ in range(n)]
for _ in range(k):
  c, d = map(int, input().split())
  blockships[c-1].append(d-1)
  blockships[d-1].append(c-1)
# assign users (id) for connected component, according to friendships
# also increment a counter for size of each component
component_id = [-1]*n
component_size = dict()
stack_to_visit = [(node, node) for node in range(n)]
while stack_to_visit:
  node, parent_id = stack_to_visit.pop()
  if component_id[node] != -1:
    continue
  component_id[node] = parent_id
  component_size[parent_id] = component_size.get(parent_id, 0) + 1
  for other in friendships[node]:
    stack_to_visit.append((other, parent_id))
# calculate number of suggestions for each node
for node in range(n):
  suggestions = 0
  current_id = component_id[node]
  suggestions += component_size[current_id] - 1
  suggestions -= len(friendships[node])
  suggestions -= sum(int(component_id[other] == current_id) for other in blockships[node])
  print(suggestions, end=" ")

Submission status: Accepted

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m, k = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    fb = [0]*n
    i = 0
    for x in sys.stdin.buffer.readlines():
        if i < m:
            a, b = map(int, x.split())
            fb[a-1] += 1
            fb[b-1] += 1
            uf.union(a-1, b-1)
        else:
            c, d = map(int, x.split())
            if uf._root(c-1) == uf._root(d-1):
                fb[c-1] += 1
                fb[d-1] += 1
        i += 1

    ans = [-uf.table[uf._root(i)]-1-fb[i] for i in range(n)]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil

class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[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
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        s = set()
        for par in self.par:
            s.add(par)
        return s
n,m,k = map(int,input().split())
uf = unionfind(n)
fr = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.unite(a-1,b-1)
    fr[a-1]+=1
    fr[b-1]+=1
ans = [uf.get_size(i) -fr[i]-1 for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    if uf.same(c-1,d-1):
        ans[c-1] -=1
        ans[d-1] -=1
print(*ans)

Submission status: Accepted

Solution code:
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())

N, M, K = map(int, input().split())

uf = UnionFind(N+1)
AB_list = []

for i in range(M):
    A, B = map(int, input().split())
    AB_list.append([A, B])
    uf.union(A, B)

dame = [[] for i in range(N+1)]
for i in range(M):
    if uf.same(AB_list[i][0], AB_list[i][1]):
        dame[AB_list[i][0]].append(AB_list[i][1])
        dame[AB_list[i][1]].append(AB_list[i][0])

for i in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        dame[C].append(D)
        dame[D].append(C)

ans_list = []
for i in range(1, N+1):
    ans_list.append(uf.size(i) - len(dame[i]) - 1)
    #print(ans, uf.size(i), len(dame[i]))
print(*ans_list)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

friends = [[] for _ in range(N + 1)]
for i in range(M):
    A, B = [int(x) for x in input().split()]
    friends[A].append(B)
    friends[B].append(A)

block = [[] for _ in range(N + 1)]
for i in range(K):
    C, D = [int(x) for x in input().split()]
    block[C].append(D)
    block[D].append(C)

G = []
check = [False] * (N + 1)
for i in range(1, N + 1):
    if check[i] == False:
        check[i] = True
        g = [i]
        q = deque([i])
        while q:
            j = q.popleft()
            for k in friends[j]:
                if check[k] == False:
                    check[k] = True
                    g.append(k)
                    q.append(k)
        G.append(g)

gr = np.array([0] * (N + 1))
fr = np.array([len(friends[i]) for i in range(N + 1)])
bl = np.array([0] * (N + 1))

for g in G:
    s = set(g)
    for v in g:
        gr[v] = len(g)
        b = set(block[v])
        bl[v] = len(s & b)

ans = gr - fr - bl - np.array([1] * (N + 1))

for i in range(1, N + 1):
    print(ans[i], end='')
    if i == N:
        print('')
    else:
        print(' ', end='')

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = 0
        self.blocks = 0


n, m, k = [int(i) for i in input().split()]

data=[1]*m
row=[]
col=[]
peoples = [People() for i in range(n + 1)]
for i in range(m):
    one, two = [int(j) for j in input().split()]
    new_one=min(one,two)
    new_two=max(one,two)
    row.append(one)
    col.append(two)
    peoples[one].frends+=1
    peoples[two].frends+=1

frends = csr_matrix((data, (row, col)), shape=(n+1, n+1))


num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks+=1
        peoples[two].blocks+=1

renketu_num = [0]*num
for i in labels:
    renketu_num[i]+=1


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return peoples[i].frends


def get_block_num(i):
    return peoples[i].blocks


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))

Submission status: Accepted

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = [[] for i in range(N)]
B = [[] for i in range(N)]
for i in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  A[a].append(b)
  A[b].append(a)
for i in range(K):
  a, b = map(lambda x:int(x)-1, input().split())
  B[a].append(b)
  B[b].append(a)
P = [-1 for i in range(N)]
Q = []
k = -1
for i in range(N):
  if P[i] == -1:
    q = 1
    k += 1
    P[i] = k
    d = deque([i])
    while len(d):
      s = d.pop()
      for t in A[s]:
        if P[t] == -1:
          P[t] = k
          q += 1
          d.append(t)
    Q.append(q)
for i in range(N):
  ans = Q[P[i]] - len(A[i]) - 1
  for j in B[i]:
    if P[i] == P[j]:
      ans -= 1
  print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
ans = [0] * N
class unionfind():
  def __init__(self, N):
    self.__N = N
    self.__parent = [-1] * (N + 1)
    
  def table(self):
    print(self.__parent)
    
  def find_parent(self, x):
    if self.__parent[x] < 0:
      return x
    else:
      self.__parent[x] = self.find_parent(self.__parent[x])
      return self.__parent[x]
    
  def union(self, x, y):
    x = self.find_parent(x)
    y = self.find_parent(y)
    if x == y :
      return
    if self.__parent[x] > self.__parent[y]:
      x, y = y, x
    self.__parent[x] += self.__parent[y]
    self.__parent[y] = x
    
  def size(self, x):
    return  -self.__parent[self.find_parent(x)]
  
  def same(self, x, y):
    if self.find_parent(x) == self.find_parent(y):
      return True
    else:
      return False

uf = unionfind(N)
for _ in range(M):
  A, B = map(int, input().split())
  uf.union(A, B)
  ans[A-1] += 1
  ans[B-1] += 1

for _ in range(K):
  C, D = map(int, input().split())
  if uf.same(C, D):
    ans[C-1] += 1
    ans[D-1] += 1

for i in range(N):
  print(uf.size(i+1) - ans[i] - 1,end=" ")

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
def size(x):
    return -par[find(x)]
g = [[] for _ in range(n+1)]
b = [[] for _ in range(n+1)]
for _ in range(m):
    s,t = map(int,input().split())
    unite(s,t)
    g[s].append(t)
    g[t].append(s)
for _ in range(k):
    s,t = map(int,input().split())
    b[s].append(t)
    b[t].append(s)
for i in range(1,n+1):
    ans = size(i)-1-len(g[i])
    for e in b[i]:
        if same(i,e):
            ans -= 1
    print(ans,end=" ")

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N, M, K = map(int, input().split())

al = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    al[a].append(b)
    al[b].append(a)

block = [[] for i in range(N+1)]
for i in range(K):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

seen = [0 for i in range(N+1)]
num_connect = [0 for i in range(N+1)]
cluster = [0 for i in range(N+1)]

def bfs(u, c):
    visited = []
    stack = deque([u])
    seen[u] = 1
    count = 1

    while len(stack) > 0:
        v = stack.popleft()
        visited.append(v)
        cluster[v] = c
        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                count += 1
                seen[w] = 1

    for v in visited:
        num_connect[v] = count

c = 1
for i in range(1,N+1):
    if seen[i] == 0:
        bfs(i, c)
        c += 1

for i in range(1,N+1):
    bl = 0
    for d in block[i]:
        if cluster[i] == cluster[d]:
            bl += 1
    print(num_connect[i] - 1 - len(al[i]) - bl, end=" ")

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N, M, K = map(int, input().split())

al = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    al[a].append(b)
    al[b].append(a)

block = [[] for i in range(N+1)]
for i in range(K):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

seen = [0 for i in range(N+1)]
num_connect = [0 for i in range(N+1)]
cluster = [0 for i in range(N+1)]

def bfs(u, c):
    visited = []
    stack = deque([u])
    seen[u] = 1
    count = 1

    while len(stack) > 0:
        v = stack.popleft()
        visited.append(v)
        cluster[v] = c
        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                count += 1
                seen[w] = 1

    for v in visited:
        num_connect[v] = count

c = 1
for i in range(1,N+1):
    if seen[i] == 0:
        bfs(i, c)
        c += 1

for i in range(1,N+1):
    bl = 0
    for d in block[i]:
        if cluster[i] == cluster[d]:
            bl += 1
    print(num_connect[i] - 1 - len(al[i]) - bl, end=" ")
print()

Submission status: Accepted

Solution code:
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())
        
n, m, k = map(int, input().split())
ans = [-1 for _ in range(n)]
UF = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    UF.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for i in range(n):
    ans[i] += UF.size(i)

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if UF.same(c, d):
        ans[c] -= 1
        ans[d] -= 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        #親の添字、親自身は木の要素数*-1をもつ
        self.root = [-1]*(n)
        #枝の最大長さ
        self.rank = [0]*(n)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    #高さによる合併    
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return 
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]    
    
    def members(self, x):
        root = self.find_root(x)
        return [i for i in range(self.n) if self.find_root(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) 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()}

N, M, K = map(int,input().rstrip().split())
AB=[list(map(int,input().rstrip().split()))for _ in range(M)]
CD=[list(map(int,input().rstrip().split()))for _ in range(K)]

u = UnionFind(N)
for a,b in AB:
    u.unite(a-1,b-1)

ans=[u.count(i)-1 for i in range(N)] #木の要素数から自分を引く
ans

for a,b in AB:
    if u.same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1

for c,d in CD:
    if u.same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set(q))
        while q:
            now = q.pop()
            seen[now] = cnt
            for next in friends[now]:
                if seen[next] != -1:
                    continue
                friends_chain[-1].add(next)
                q.append(next)
        cnt += 1

    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        print(tmp_ans, end=' ')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
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())
uf=UnionFind(n)
arr=[0]*n
for i in range(m):
    a,b=map(int, input().split())
    uf.union(a-1,b-1)
    arr[a-1]+=1
    arr[b-1]+=1
for i in range(k):
    c,d=map(int, input().split())
    if uf.same(c-1,d-1):
        arr[c-1]+=1
        arr[d-1]+=1
for i in range(n):
    print(uf.size(i)-arr[i]-1)