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):
        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)
cnt = [0]*(N+1)
cnt2 = [[] for _ in range(N+1)]
ans = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1,B-1)
    cnt[A] += 1
    cnt[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    cnt2[D].append(C)
    cnt2[C].append(D)
for i in range(N):
    tmp = 0
    for k in cnt2[i+1]:
        if uf.same(k-1,i):
            tmp += 1
    ans[i] = uf.size(i)-1-cnt[i+1]-tmp
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M,K = map(int,input().split())
fr = [[] for _ in range(N)]
br = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for _ in range(K):
    c,d = map(int,input().split())
    br[c-1].append(d-1)
    br[d-1].append(c-1)
used = [-1]*N #-1なら未探索。数字はrenketuのindex
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(fr,i,-1,index,li)
    index += 1
    renketu.append(li)
ans = [0]*N
for i in range(N):
    ans[i] = len(renketu[used[i]])-1
for i in range(N):
    li1 = fr[i]
    li2 = br[i]
    for j1 in li1:
        if i < j1:
            if used[i] == used[j1]:
                ans[i] -= 1
                ans[j1] -= 1
    for j2 in li2:
        if i < j2:
            if used[i] == used[j2]:
                ans[i] -= 1
                ans[j2] -= 1
print(*ans)

Submission status: Accepted

Solution code:
from  collections import deque,Counter
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visited=[0 for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
time=0
for j in range(1,N+1):
    if visited[j]==0:
        stack=deque([j])
        time+=1
        visited[j]=time
        while stack:
            x=stack.popleft()
            for i in graph_ab[x]:
                if visited[i]==0:
                    visited[i]=time
                    stack.append(i)
#     visit_list[j]=visited
counter=Counter(visited) 
for i in range(K):
    c,d=CD[i]
    if visited[c]==visited[d]:
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=counter[visited[i]]-len(graph_ab[i])-len(graph_cd[i])-1

del user[0]
print(*user)

Submission status: Accepted

Solution code:

import copy
import itertools
import sys
sys.setrecursionlimit(10**5)
def addp(a, i, j):
    tmp1 = searchp(a, i)
    tmp2 = searchp(a, j)
    if(tmp1 != tmp2):
        a[tmp2][0] = tmp1
        a[tmp1][1] += a[tmp2][1]

def searchp(a, i):
    if(a[i][0]==i):
        return i
    else:
        tmp = searchp(a, a[i][0])
        a[i][0] = tmp
        return tmp
n, m, k = map(int, input().split())

clist = [[1] * 2 for i in range(n)]

for i in range(n):
    clist[i][0] = i
flist = [[0] * 2 for i in range(m)]
blist = [[0] * 2 for i in range(k)]
for i in range(m):
    flist[i] = list(map(int, input().split()))
for i in range(k):
    blist[i] = list(map(int, input().split()))
for i in range(m):
    addp(clist, flist[i][0]-1, flist[i][1]-1)
for i in range(n):
    if(clist[i][0] != i):
        tmp = searchp(clist, i)
        clist[i][0] = tmp
        clist[i][1] = clist[tmp][1]
for i in range(m):
    if(searchp(clist, flist[i][0]-1) == searchp(clist, flist[i][1]-1)):
        clist[flist[i][0]-1][1] -= 1
        clist[flist[i][1]-1][1] -= 1
for i in range(k):
    if(searchp(clist, blist[i][0]-1) == searchp(clist, blist[i][1]-1)):
        clist[blist[i][0]-1][1] -= 1
        clist[blist[i][1]-1][1] -= 1
for i in range(n):
    print(clist[i][1]-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):
        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())
retu_n=[0]*N
block_n=[0]*N
uf = UnionFind(N)


for m in range(M):
  a,b=map(int,input().split())
  retu_n[a-1] +=1
  retu_n[b-1] +=1
  uf.union(a-1,b-1)
  
  
for k in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1, d-1):
    block_n[c-1] += 1
    block_n[d-1] += 1
    
  
for n in range(N):
  print(uf.size(n)-retu_n[n]-block_n[n]-1, end=" ")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]


N,M,K=map(int,input().split())
retu_n=[0]*N
block_n=[0]*N
uf = UnionFind(N)

for m in range(M):
  a,b=map(int,input().split())
  retu_n[a-1] +=1
  retu_n[b-1] +=1
  uf.unite(a,b)
  
  
for k in range(K):
  c,d=map(int,input().split())
  if uf.same(c, d):
    block_n[c-1] += 1
    block_n[d-1] += 1
    
  
for n in range(N):
  print(uf.size(n+1)-retu_n[n]-block_n[n]-1, end=" ")

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]


N,M,K=map(int,input().split())
retu_n=[0]*N
block_n=[0]*N
uf = UnionFind(N)

for m in range(M):
  a,b=map(int,input().split())
  retu_n[a-1] +=1
  retu_n[b-1] +=1
  uf.unite(a,b)
  
  
for k in range(K):
  c,d=map(int,input().split())
  if uf.same(c, d):
    block_n[c-1] += 1
    block_n[d-1] += 1
    
  
for n in range(N):
  print(uf.size(n+1)-retu_n[n]-block_n[n]-1, end=" ")

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, comp_id, comp_cnt):
    i = 0
    cnt = 0
    for v in range(len(G)):
        if comp_id[v] != -1:
            continue
        comp_id[v] = i
        cnt += 1
        stack = deque([v])
        while stack:
            v = stack.pop()
            for c in G[v]:
                if comp_id[c] != -1:
                    continue
                comp_id[c] = i
                cnt += 1
                stack.append(c)
        comp_cnt.append(cnt)
        cnt = 0
        i += 1


def main():
    N, M, K = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        G[A].append(B)
        G[B].append(A)
    B = [[] for _ in range(N)]
    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        B[C].append(D)
        B[D].append(C)

    # connected component
    comp_id = [-1] * N
    comp_cnt = []
    dfs(G, comp_id, comp_cnt)

    ans = [-1] * N
    for i in range(N):
        c_id = comp_id[i]
        n_neighbor = len(G[i])
        n_block = len(B[i])
        for j in B[i]:
            if c_id != comp_id[j]:
                n_block -= 1
        ans[i] = comp_cnt[c_id] - 1 - n_neighbor - n_block
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            if p in d:
                d[p].append(i)
            else:
                d[p] = [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(int)
    e = defaultdict(int)
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a] += 1
        d[b] += 1
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        if u.same(a, b):
            e[a] += 1
            e[b] += 1
    ans = [0] * n
    for i, v in u.all_group_members().items():
        x = len(v) - 1
        for j in v:
            ans[j] = x-d[j] - e[j]
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:

from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = [0]*n
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            for i in dfs(fr,v,temp,visited):
                cc[i] = dfs(fr,v,temp,visited)
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N + 1)]
        self.friendcount = [1] * (N + 1)

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

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x)
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.friendcount = [1] * N

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

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x)
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))

Submission status: Accepted

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

    def find(self, x):  #要素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が属するグループと要素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):   #要素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())
friend = UnionFind(n + 1)

a, b = [], []
num = [0] * (n + 1)
for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    num[aa] += 1
    num[bb] += 1
    friend.union(aa, bb)

c,d = [],[]
for i in range(k):
    cc, dd = map(int, input().split())
    c.append(cc)
    d.append(dd)

ans = [0] * (n + 1)
for i in range(1, n + 1):
    ans[i] = friend.size(i)
    ans[i] -= num[i]
    ans[i] -= 1

for i in range(k):
    if friend.same(c[i], d[i]):
        ans[c[i]] -= 1
        ans[d[i]] -= 1

for i in range(1, n + 1):
    print(ans[i],end=" ")

Submission status: Accepted

Solution code:


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

uf = UnionFind(N+1)

friends = [0]*(N+1)
for A, B in AB:
    friends[A] += 1
    friends[B] += 1
    uf.Unite(A, B)

ans = [0]*(N+1)
for i in range(1, N+1):
    ans[i] = uf.Count(i)-1-friends[i]

for C, D in CD:
    if uf.isSameGroup(C, D):
        ans[C] -= 1
        ans[D] -= 1

print(*ans[1:])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] = self.par[y] + self.par[x]
        self.par[y] = x

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.par[self.find(x)]
    
    

n, m, k = map(int, input().split())
U = UnionFind(n)
fl = [0] * n
bl = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    U.union(a - 1, b - 1)
    fl[a - 1] += 1
    fl[b - 1] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if U.same_check(c - 1, d - 1):
        bl[c - 1] += 1
        bl[d - 1] += 1

ans_list = []
for i in range(n):
    ans = -U.size(i) - fl[i] - bl[i] - 1
    ans_list.append(ans)
print(*ans_list)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')


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 solve():
    n, m, k = MI()
    uf = UnionFind(n)

    friends = [0] * n
    for i in range(m):
        a, b = MI1()
        uf.union(a, b)
        friends[a] += 1
        friends[b] += 1
    # print(uf.__str__())
    # print(friends)

    blocks = [0] * n
    for i in range(k):
        c, d = MI1()
        if uf.same(c, d):
            blocks[c] += 1
            blocks[d] += 1

    # print(blocks)

    ans = [0] * n

    for i in range(n):
        ans[i] = uf.size(i) - 1 - blocks[i] - friends[i]
        # print(ans)

    print(' '.join(list(map(str, ans))))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')


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 solve():
    n, m, k = MI()
    uf = UnionFind(n)

    friends = [0] * n
    for i in range(m):
        a, b = MI1()
        uf.union(a, b)
        friends[a] += 1
        friends[b] += 1
    # print(uf.__str__())
    # print(friends)

    # blocks = [[0] * n for _ in range(n)]

    blocks = {}
    for i in range(k):
        c, d = MI1()
        # blocks[c][d] += 1
        # blocks[d][c] += 1
        blocks.setdefault(c, [])
        blocks[c].append(d)

        blocks.setdefault(d, [])
        blocks[d].append(c)

    # print(blocks)

    ans = [0] * n

    for i in range(n):
        # print(i, uf.size(i))
        block = 0
        # print('  bb', blocks.get(i))
        for bb in blocks.get(i, []):
            # print(bb)
            if uf.same(i, bb):
                # print(idx, bb, uf.find(idx), uf.same(idx, i))
                block += 1
        ans[i] = uf.size(i) - 1 - block - friends[i]
        # print(ans)

    print(' '.join(list(map(str, ans))))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import copy

N, M, K = map(int, input().split())
friend = [deque() for _ in range(N)]
status = [-1]*N
numList = [0]*N
ans = [0]*N

for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    ans[a-1] -= 1
    ans[b-1] -= 1

def DFS(graph, v, num):
    cnt = 0
    stack = [v]
    status[v] = num
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if status[w] == -1:
                status[w] = num
                cnt += 1
                stack.append(w) 
        else:
            stack.pop() 
    numList[num] = cnt

cnt = 0
for i in range(N):
    if status[i] == -1:
        DFS(friend, i, cnt)
        cnt += 1

for i in range(N):
    ans[i] += numList[status[i]]

for i in range(K):
    a, b = map(int, input().split())
    if status[a-1] == status[b-1]:
        ans[a-1] -= 1
        ans[b-1] -= 1

print(" ".join(map(str, ans)))