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:
import sys
sys.setrecursionlimit(200100)

def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    bl = []
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl.append((c,d))

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb] += 1
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    ans = [0] * N
    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1:
            ans[i] = gr[label[i]]
            continue
        gr.append(0)
        dfs(i, lb)
        ans[i] = gr[label[i]]
        lb += 1

    for c, d in bl:
        if label[c] == label[d]:
            ans[c] -= 1
            ans[d] -= 1

    for i in range(N):
        ans[i] -= len(fr[i]) + 1

    print(*ans, sep=' ')

abc157_d()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, num):
        self.par = list(range(1,num+1))
        self.size = [1]*num
    
    def root(self, n):
        if self.par[n-1] != n:
            self.par[n-1] = self.root(self.par[n-1])
        return self.par[n-1]

    def unite(self, a, b):
        a=self.root(a)
        b=self.root(b)
        if a!=b:
            self.par[b-1]=a
            self.size[a-1] += self.size[b-1]
        return
    
    def get_size(self, n):
        return self.size[self.root(n)-1]


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    fris = [0]*N
    blos = [0]*N

    union = UnionFind(N)
    for ai, bi in zip(A, B):
        union.unite(ai,bi)
        fris[ai-1]+=1
        fris[bi-1]+=1
    
    for ci, di in zip(C, D):
        if union.root(ci) == union.root(di):
            blos[ci-1]+=1
            blos[di-1]+=1
    
    ans = [0]*N
    for i in range(1,N+1):
        s = union.get_size(i)
        s -= fris[i-1]
        s -= blos[i-1]
        s -= 1
        ans[i-1] = s

    print(*ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
N,M,K = map(int, input().split())
V = []

color = [-1]*N
V_block = []

#各連結成分の次元テーブル
dic = {}

dim = 0
#深さ優先探索
def dfs(node, c):
    global dim

    if color[node]!=-1:
        return
    color[node] = c
    dim = dim + 1
    for next_node in V[node]:
        dfs(next_node, c)
    return

for _ in range(N):
    V.append(set())
    V_block.append(set())
for _ in range(M):
    a,b = map(int, input().split())
    V[a-1].add(b-1)
    V[b-1].add(a-1)

#一旦捨てる
for _ in range(K):
    c,d = map(int, input().split())
    V_block[c-1].add(d-1)
    V_block[d-1].add(c-1)
    
c = 0
for node in range(N):
    if color[node]!=-1:
        continue
    dim = 0
    dfs(node, c)
    dic[c] = dim

    c = c + 1

ans_list = []
for node in range(N):
    num = 0
    for block_node in V_block[node]:
        if color[node]==color[block_node]:
            num = num + 1
    ans_list.append(dic[color[node]]-num-len(V[node])-1)

print(*ans_list)

Submission status: Accepted

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        stack = [person]
        while stack:
            new = stack.pop()
            visited[new] = True
            net_leaders[new] = person
            network.add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)
        networks[person] = network

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
stack = deque()
ans = [0]*(n+1)
visited = [0]*(n+1)
for i in range(1, n+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in friend[n]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & friend[i]) - len(link & block[i]) -1
print(*ans[1:])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

    def root(self, x):
        '''
        xの根を返す
        '''
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        二つの木を合併する
        '''
        x = self.root(x)
        y = self.root(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):
        '''
        xが属する木のサイズを返す
        '''
        return -self.parents[self.root(x)]

    def same(self, x, y):
        '''
        xとyが同じ木に属するかを調べる
        '''
        return self.root(x) == self.root(y)

    def members(self, x):
        '''
        xの木のリストを返す
        '''
        root = self.root(x)
        return [i for i in range(self.n) if self.root(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())
if M:
    AB = [map(int, input().split()) for _ in range(M)]
    A, B = [list(i) for i in zip(*AB)]
if K:
    CD = [map(int, input().split()) for _ in range(K)]
    C, D = [list(i) for i in zip(*CD)]


friend = [[] for i in range(N)]
block = [[] for i in range(N)]

uf = UnionFind(N)

if M:
    for i in range(M):
        uf.union(A[i]-1, B[i]-1)
        friend[A[i]-1].append(B[i]-1)
        friend[B[i]-1].append(A[i]-1)

if K:
    for i in range(K):
        block[C[i]-1].append(D[i]-1)
        block[D[i]-1].append(C[i]-1)

for i in range(N):
    tmp = uf.size(i)-1
    for v in friend[i]:
        if uf.same(i, v):
            tmp -= 1
    for v in block[i]:
        if uf.same(i, v):
            tmp -= 1

    print(tmp)

Submission status: Accepted

Solution code:
def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1 - len(fr[i])
  for j in bl[i]:
    if roots[j]==roots[i]:
      ans[i] -= 1      
      
print(*ans)

Submission status: Accepted

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

F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for i, j in AB:
    F[i - 1].add(j - 1)
    F[j - 1].add(i - 1)
for i, j in CD:
    B[i - 1].add(j - 1)
    B[j - 1].add(i - 1)

Q = deque()
S = [0] * N
d = [0] * N

for i in range(N):
    if d[i] != 0:
        continue
    L = {i}
    d[i] = 1
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in F[q]:
            if d[j] == 0:
                d[j] = 1
                Q.append(j)
                L.add(j)
    for k in L:
        S[k] = len(L) - len(L & F[k]) - len(L & B[k]) - 1

print(*S)

Submission status: Accepted

Solution code:
from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
R=[0]*n

for i in range(n):
    if D[i]:
        continue
    que=deque([])
    que.append(i)
    S=set()
    S.add(i)
    while que:
        p=que.popleft()
        for np in F[p]:
            if D[np]!=1:
                que.append(np)
                S.add(np)
                D[np]=1
    for s in S:
        R[s]=len(S)-len(F[s])-len(S&B[s])-1

print(*R)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):      #初期化
        self.n = n
        # 親
        self.parents = [i for i in range(n)]
        # 木の深さ
        self.ranks = [0] * n
        # グループの要素数
        self.sizes = [1] * n

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parents[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x]==self.ranks[y]:
                self.ranks[x] += 1

    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 size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    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 = map(int, input().split())
    uf = UnionFind(N)
    dic = {i:set([i]) for i in range(N)}
    fcnt = {i:0 for i in range(N)}

    for i in range(M):
        a,b = map(int,input().split())
        uf.unite(a-1, b-1)
        fcnt[a-1] += 1
        fcnt[b-1] += 1

    for j in range(K):
        a,b = map(int,input().split())
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    ret = [None]*N
    for i in range(N):
        ret[i] = uf.size(i)-fcnt[i]
        for x in dic[i]:
            if uf.same(x,i):
                ret[i] -= 1
#    ret = [len(uf.members(i) - dic[i]) for i in range(N)]
    print(" ".join(map(str,ret)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    return


def main():
    N, M, K = map(int, input().split())
    connection = [[] for _ in range(N)]
    uf = UnionFind(N)
    for i in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        connection[a].append(b)
        connection[b].append(a)
        uf.union(a, b)

    for i in range(K):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.same(c, d):
            connection[c].append(d)
            connection[d].append(c)

    ans = []
    for i in range(N):
        ans.append(uf.size(i) - len(connection[i]) - 1)
    L = [str(i) for i in ans]
    print(" ".join(L))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    ans = [0] * n
    for _ in range(m):
        A, B = map(int, input().split())
        A, B = A - 1, B - 1
        uf.union(A, B)
        ans[A] -= 1
        ans[B] -= 1

    for i in range(n):
        ans[i] = ans[i] + uf.size(i) - 1

    for _ in range(k):
        C, D = map(int, input().split())
        C, D = C - 1, D - 1
        if uf.same(C, D):
            ans[C] -= 1
            ans[D] -= 1
    
    print(*ans)
    
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()}

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M, K = map(int, input().split())
G = [[] for i in range(N)]
NG = [set() for i in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A - 1].append(B - 1)
    G[B - 1].append(A - 1)
    NG[A - 1].add(B - 1)
    NG[B - 1].add(A - 1)

for _ in range(K):
    A, B = map(int, input().split())
    NG[A - 1].add(B - 1)
    NG[B - 1].add(A - 1)
C = [-1] * N
CNT = [0] * N
c = 0
for i in range(N):
    if C[i] >= 0: continue
    Q = [i]
    C[i] = c
    CNT[c] += 1
    while Q:
        x = Q.pop()
        for y in G[x]:
            if C[y] == -1:
                C[y] = C[x]
                CNT[C[y]] += 1
                Q.append(y)
    c +=1
Y = [0] * N
for i in range(N):
    Y[i] = CNT[C[i]] - 1
for i in range(N):
    for j in NG[i]:
        if C[i] == C[j]:
            Y[i] -= 1
print(*Y)

Submission status: Accepted

Solution code:
from collections import deque

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

#listを組むより早い
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

for i in range(k):
    c, d = map(int, input().split())
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)

q = deque()
ans = [0] * n
visited = [0] * n

for i in range(n):
    if visited[i]:
        continue
    #集合を構築していく
    group = {i}
    visited[i] = 1
    q.append(i)
    while q:
        k = q.popleft()
        for j in friends[k]:
            if not visited[j]:
                q.append(j)
                group.add(j)
                visited[j] = 1
    
    # できた集合内でとりあえず計算
    for l in group:
        ans[l] = len(group) - len(blocks[l] & group) - len(friends[l] & group) - 1
print(*ans)
#print(*ans,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

friend_sum = [[] for i in range(n)]
block = []
block_sum = [[] for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    if a > b:
        a, b = b, a
    friend_sum[a-1].append(b-1)
    friend_sum[b-1].append(a-1)

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

label = 0
g_label = [0 for i in range(n)]
g_list = [0 for i in range(n)]

for i in range(n):
    if g_label[i] == 0:
        label += 1
        g_label[i] = label
        g_list[label-1] += 1
        q = deque([])
        q.append(i)
        while len(q) != 0:
            num = q.popleft()
            for j in range(len(friend_sum[num])):
                if g_label[friend_sum[num][j]] == 0:
                    g_label[friend_sum[num][j]] = label
                    g_list[label-1] += 1
                    q.append(friend_sum[num][j])

ans = 0

for i in range(n):
    ans = g_list[g_label[i]-1] - len(friend_sum[i]) - 1
    for j in range(len(block_sum[i])):
        if g_label[i] == g_label[block_sum[i][j]]:
            ans -= 1
    print(ans, end=' ')

print()

Submission status: Accepted

Solution code:
# AC: 753 msec(Python3)
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.size = [1] * (n+1)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        return self.size[self.find(x)]


def main():
    N,M,K,*uv = map(int, read().split())
    ab, cd = uv[:2*M], uv[2*M:]

    uf = UnionFind(N)
    friend = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(ab)]*2):
        uf.unite(a, b)
        friend[a].append(b)
        friend[b].append(a)
    
    ans = [uf.get_size(i) - 1 - len(friend[i]) for i in range(N+1)]

    for c, d in zip(*[iter(cd)]*2):
        if uf.is_same(c, d):
            ans[c] -= 1
            ans[d] -= 1
    
    print(*ans[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.size = [1] * (n+1)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        return self.size[self.find(x)]


def main():
    N,M,K,*uv = map(int, read().split())
    ab, cd = uv[:2*M], uv[2*M:]

    uf = UnionFind(N)
    friend = [set() for _ in range(N+1)]
    for a, b in zip(*[iter(ab)]*2):
        uf.unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    
    ans = [uf.get_size(i) - 1 - len(friend[i]) for i in range(N+1)]

    for c, d in zip(*[iter(cd)]*2):
        if uf.is_same(c, d):
            ans[c] -= 1
            ans[d] -= 1
    
    print(*ans[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n,m,k=map(int,input().split())
fre=[[]for _ in range(n)]
blo=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    blo[c-1].append(d-1)
    blo[d-1].append(c-1)

cnt=[0]*n
l=deque()
x=1
dic={}
for i in range(n):
    if cnt[i]==0:
        l.append(i)
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=x
                if x in dic:
                    dic[x]+=1
                else:
                    dic[x]=1
                l.append(to)
    x+=1

for i in range(n):
    if dic=={}:
        print(0)
    else:
        k=len(fre[i])
        for b in blo[i]:
            if cnt[b]==cnt[i]:
                k+=1
        if cnt[i] in dic:
            print(dic[cnt[i]]-k-1)
        else:
            print(0)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(set)
block = defaultdict(set)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].add(d)
    block[d].add(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(set)
seen = [0]*n


for i in range(n):
    if not seen[i]==0:
        continue
    seen[i] = i+1
    roopname.append(i+1)
    roop[i+1].add(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==0:continue
        seen[p-1] = i+1
        roop[i+1].add(p)
        for j in friends[p]:
            if seen[j-1]==0:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = [len(roop[seen[i]])-len(roop[seen[i]]&friends[i+1])-len(roop[seen[i]]&block[i+1])-1 for i in range(n)]

    

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,M,K = map(int,S().split())
friend = [LI() for i in range(M)]
enemy = [LI() for i in range(K)]

from collections import deque,defaultdict,Counter

G = defaultdict(list)

for a,b in friend:
    G[a].append(b)
    G[b].append(a)

A = [0]*(N+1)  #根

for i in range(1,N+1):
    if A[i] != 0:
        continue
    else:
        A[i] = i
        q = deque([i])
        while q:
            n = q.pop()
            for j in G[n]:
                if A[j] == 0:
                    A[j] = i
                    q.append(j)

c = Counter(A)

A = [[A[i],c[A[i]]] for i in range(N+1)]  #(根,連結成分の大きさ)

#同じ連結成分の中の友達関係、敵対関係の分だけ引く

for a,b in friend:
    if A[a][0] == A[b][0]:
        A[a][1] -= 1
        A[b][1] -= 1
for c,d in enemy:
    if A[c][0] == A[d][0]:
        A[c][1] -= 1
        A[d][1] -= 1

print(*[A[i][1]-1 for i in range(1,N+1)])

#-1は自分自身

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    r = [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(abcd[:2 * m])] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        uf.t[i] = i if v < 0 else v
    mp = {k: set([]) for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].add(i)
    for c, d in zip(*[iter(abcd[2 * m:])] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, K = ZZ()
    F = [0] * (N+1)
    output = []

    par = [i for i in range(N+1)]
    rank = [0] * (N+1)

    # 要素xの親ノードを返す
    def find(x):
        if par[x] == x:
            return x
        par[x] = find(par[x])
        return par[x]

    # 要素x, yの属する集合を併合
    def unite(x, y):
        x, y = find(x), find(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return

    # xとyが同じ集合に属するか？
    def same(x, y):
        return find(x) == find(y)

    for _ in range(M):
        a, b = ZZ()
        F[a] += 1
        F[b] += 1
        unite(a, b)

    for i in range(1, N+1): find(i)
    cnt = collections.Counter(par)

    for _ in range(K):
        c, d = ZZ()
        if same(c, d):
            F[c] += 1
            F[d] += 1
    for i in range(1, N+1):
        cc = cnt[par[i]] - F[i] - 1
        output.append(cc)

    print(*output)

    return

if __name__ == '__main__':
    main()