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
input=sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if D not in d[C]:
                e[C] += 1
            if C not in d[D]:
                e[D] += 1
    
    g = lambda x:uft.getsize(x)-e[x]-f[x]-1
    print(*map(g, range(1, N+1)))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if not D in d[C]:
                e[C] += 1
            if not C in d[D]:
                e[D] += 1

    print(*(uft.getsize(i)-e[i]-f[i]-1 for i in range(1, N+1)))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

"""
Union-Find木実装のキモ(計算量削減)
1. Unionの工夫
   マージテク：大きい方を動かさずに小さい方をくっつける
2. Findの工夫
   経路圧縮 : 集合の要素を根に直接つなぎ変える.木をフラットにする.
"""

# Union-Findを用いて連結成分を考える(Union-Find木の実装)
class UnionFind:
    # まずは最初の状態を作る
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0

    # そのノードの根を返す過程で,集合の要素を根に直接つなぎかえる
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    # aとbの根が同じ,つまり同じ連結成分内かどうかを返す
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    # 連結成分同士を効率的に(rankが大きい方を動かさずにrankが小さい方をくっつける)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

blocks = [[] for _ in range(N)]
for c, d in CD:
    c, d = c-1, d-1
    blocks[c].append(d)
    blocks[d].append(c)

# friendsは友達の数を保持する
friends = [0] * N
uf = UnionFind(N)
for a,b in AB:
    a, b = a-1, b-1
    friends[a] += 1
    friends[b] += 1
    # aとbが同連結成分内であれば何もする必要がない
    if uf.is_same(a, b): continue
    # 異なれば結合
    uf.unite(a, b)

for i in range(N):
    uf.root(i)

from collections import Counter
ctr = Counter()
for i in range(N):
    r = uf.root(i)
    ctr[r] += 1

ans = []
for i in range(N):
    tmp = ctr[uf.root(i)] - friends[i] -1
    for b in blocks[i]:
        if uf.is_same(i, b):
            tmp -= 1
    ans.append(tmp)
print(*ans)

Submission status: Accepted

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

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

    # xとyの属する集合の併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # sizeの大きいほうがx
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x

    # xとyが同じ集合に属するかの判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが属する集合の個数
    def size(self, x):
        return -self.parent[self.find(x)]


n, m, k = map(int, input().split())
num_friends = [0 for _ in range(n + 1)]
blocks = [[] for _ in range(n + 1)]
uf = UnionFind(n + 1)

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

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

out = ''
for i in range(1, n + 1):
    ans = uf.size(i) - num_friends[i] - 1
    for block in blocks[i]:
        if uf.same(i, block):
            ans -= 1
    out += str(ans) + ' '
print(out.strip())

Submission status: Accepted

Solution code:
 # 同じ木に属する(==そこまでたどりつけるかどうか）の判定にunionfind
# 同じ木に属しているノードはあとで数えることができる（そうだね）
# 除外するやつが出てくる。直の友達+ブロック関係にあるやつ（と自分）
# 同じ木に属しているノードの総数 - (直の友達+ブロック関係+自分自身)が答え
from sys import setrecursionlimit
setrecursionlimit(10**8)
n, m, k = map(int, input().split())
par = [i for i in range(n)]
ans = [0 for _ in range(n)]


def root(x):
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(x, y):
    if x > y:
        x, y = y, x
    rx, ry = root(x), root(y)
    if rx != ry:
        par[ry] = rx


friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for _ in range(k):
    c, d = map(int, input().split())
    blocks[c - 1].append(d - 1)
    blocks[d - 1].append(c - 1)

# 木に属しているやつを数えるぜ
group_count = [0 for _ in range(n)]
for i in range(n):
    group_count[root(i)] += 1
# 答えを作るぜ
for i in range(n):
    # 初期化（じゃないけど）
    ans[i] += group_count[root(i)]
    # 直の友達を除く
    ans[i] -= len(friends[i])
    # ブロックしてるやつを除く
    for b in blocks[i]:
        ra, rb = root(i), root(b)
        if ra == rb:
            ans[i] -= 1
    # 自分自身を除く
    ans[i] -= 1
print(" ".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [0] * n

  def root(self, x):
    if self.parents[x] == x:
      return x
    else:
      y = self.root(self.parents[x])
      self.parents[x] = y
      return y

  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
    if self.ranks[x] < self.ranks[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1

n, m, k = map(int, input().split())
u = UnionFind(n)
counts = [1 for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  u.unite(a - 1, b - 1)
  counts[a - 1] += 1
  counts[b - 1] += 1

for _ in range(k):
  a, b = map(int, input().split())
  if u.same(a - 1, b - 1):
    counts[a - 1] += 1
    counts[b - 1] += 1

groups = defaultdict(int)
for i in range(n):
  groups[u.root(i)] += 1

print(*[groups[u.root(i)] - counts[i] for i in range(n)])

Submission status: Accepted

Solution code:
"""
unioufind
集合の中で、直接の友達 と直接のブロックを引く
TLE

bfsで集合をまず見ておく
"""
from collections import deque
from collections import defaultdict
N,M,K = map(int, input().split())

# 木構造を作る
G = defaultdict(list)
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

tomodachi_group = defaultdict(int)
used = [False] * N
parent = [-1] * N
group_cnt = {}
for i in range(N):
    if used[i]: continue
    used[i] = True
    parent[i] = i
    q = deque([])
    q.append(i)
    cnt = 0
    while len(q) > 0:
        a = q.popleft()
        Vs = G[a]
        for u in Vs:
            if not used[u]:
                q.append(u)
                parent[u] = i
                used[u] = True
                cnt += 1
    group_cnt[i] = cnt

block = defaultdict(int)
for i in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    # 友達グループじゃないと無意味
    if parent[c] != parent[d] :continue
    block[c] += 1
    block[d] += 1

ans = []
for i in range(N):
    cnt = group_cnt[parent[i]] - len(G[i]) - block[i]
    ans.append(cnt)
print(*ans)

Submission status: Accepted

Solution code:
n,q,qq=map(int,input().split())

# root番号保持
root = list(range(n))
# 階層保持
rank =  [0] * n
# ノード数
node =  [1] *n
minus_node =  [0] *n


def find_set(x):
    if(x != root[x]):
        root[x] = find_set(root[x])
    return root[x]

def unite(x,y):
    link(find_set(x),find_set(y))

def link(x,y):
    if root[x] == root[y]:return
    if rank[x] > rank[y]:
        root[y] =x
        node[x] += node[y] 
    else:
        root[x] = y
        node[y] += node[x] 
        if rank[x] == rank[y]:
            rank[y] +=1

def same(x,y):
    return find_set(x) == find_set(y)

# print(root)
# print(rank)
# print(node)


for _ in range(q):
    a,b = map(int,input().split())

    unite(a-1,b-1)
    minus_node[a-1] +=1
    minus_node[b-1] +=1
    # print()
    # print(root)
    # print(rank)
    # print(node)

for _ in range(qq):
    a,b = map(int,input().split())

    if same(a-1,b-1):
        minus_node[a-1] +=1
        minus_node[b-1] +=1
# print()
# print(root)
# print(rank)
# print(node)


print(" ".join([str(node[find_set(i)] - minus_node[i] -1) for i in range(n)]))

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#根なら-size,子なら親の頂点
n,m,k = [int(i) for i in input().split()]
par = [-1]*n
ans = [-1]*n

import sys
input = sys.stdin.readline

for _ in range(m):
  a,b = [int(j) for j in input().split()]
  unite(a-1,b-1)
  ans[a-1] -= 1
  ans[b-1] -= 1

for _ in range(k):
  c,d = [int(i) for i in input().split()]
  if same(c-1,d-1):
    ans[c-1] -= 1
    ans[d-1] -= 1
    
for i in range(n):
  ans[i] += size(i)
  
ans = list(map(str,ans))
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

class UF(object):
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = y = self.find(self.par[x])
            return y

    # x と y の集合を結合する
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                px, py = py, px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
            self.par[py] = px
            self.size[px] += self.size[py]
            return

    # x と y が同じ集合に属するか判定する
    def is_same(self,x,y):
        return self.find(x) == self.find(y)

    # x が属する集合の要素数を返す
    def get_size(self,x):
        return self.size[self.find(x)]

N,M,K = LI()
A,B = LIR(M,2)
C,D = LIR(K,2)
 
b = defaultdict(set)
t = defaultdict(set)
 
uf = UF(N)
 
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    t[A[i]-1].add(B[i]-1)
    t[B[i]-1].add(A[i]-1)
    
num = [0]*N
for i in range(K):
    if uf.is_same(C[i]-1, D[i]-1):
        num[C[i]-1] -= 1
        num[D[i]-1] -= 1
        
ans = []
for i in range(N):
    ans.append(uf.get_size(i)-1-len(t[i])+num[i])
print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

class UF(object):
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = y = self.find(self.par[x])
            return y

    # x と y の集合を結合する
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                px, py = py, px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
            self.par[py] = px
            self.size[px] += self.size[py]

    # x と y が同じ集合に属するか判定する
    def is_same(self,x,y):
        return self.find(x) == self.find(y)

    # x が属する集合の要素数を返す
    def get_size(self,x):
        return self.size[self.find(x)]

N,M,K = LI()
A,B = LIR(M,2)
C,D = LIR(K,2)
 
b = defaultdict(set)
t = defaultdict(set)
 
uf = UF(N)
 
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    t[A[i]-1].add(B[i]-1)
    t[B[i]-1].add(A[i]-1)
    
num = [0]*N
for i in range(K):
    if uf.is_same(C[i]-1, D[i]-1):
        num[C[i]-1] -= 1
        num[D[i]-1] -= 1
        
ans = []
for i in range(N):
    ans.append(uf.get_size(i)-1-len(t[i])+num[i])
print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

class Node:
    def __init__(self, id):
        self.id = id
        self.label = None
        self.friends = []
        self.blocks = []

sys.setrecursionlimit(10**9)
N,M,K = [int(i) for i in input().split()]

nodes = [Node(i) for i in range(N)]

for _ in range(M):
    a,b = [int(i) for i in input().split()]
    nodes[a-1].friends.append(b-1)
    nodes[b-1].friends.append(a-1)

for _ in range(K):
    c,d = [int(i) for i in input().split()]
    nodes[c-1].blocks.append(d-1)
    nodes[d-1].blocks.append(c-1)

def dfs(nodes, i, label):
    if nodes[i].label is None:
        nodes[i].label = label
        for j in nodes[i].friends:
            dfs(nodes, j, label)
        
        #for j in nodes[i].blocks:
        #    dfs(nodes, j, label)

label = 0
for i in range(len(nodes)):
    dfs(nodes, i, label)
    label+=1

node_cnts = [0] * (label+1)
for i in range(len(nodes)):
    node_cnts[nodes[i].label] += 1
            
#print(*node_cnts)
result = [0] * len(nodes)
for node in nodes:
    #print(node.id, node.label, node.friends, node.blocks)
    b_cnt = 0
    for b in node.blocks:
        if nodes[b].label == node.label:
            b_cnt += 1
            
    result[node.id] = node_cnts[node.label] - len(node.friends) - b_cnt - 1

print(*result)

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)
from collections import defaultdict
dic = defaultdict(int)


for _ in range(m):
    a,b = map(int,input().split())
    uf.union(a-1, b-1)
    dic[a-1] += 1
    dic[b-1] += 1
for _ in range(k):
    c,d = map(int,input().split())
    if uf.same(c-1, d-1):
        dic[c-1] += 1
        dic[d-1] += 1

for i in range(n):
    print(uf.size(i) - dic[i]-1)

Submission status: Accepted

Solution code:
import copy
from collections import deque,Counter
N,M,K=map(int,input().split())
friend=[[] for _ in range(N)]
block=[[] for _ in range(N)]
for i in range(M):                  #このようにすれば
    a,b=map(int,input().split())
    friend[a-1].append(b-1)         #友達リストも
    friend[b - 1].append(a - 1)
for i in range(K):
    a,b=map(int,input().split())
    block[a-1].append(b-1)          #ブロックリストも
    block[b - 1].append(a - 1)      #作れてしまう
#最初の例だとfriend:[[1,2][0,2][0,1,3][2]]block:[[][][][0]]となる
#木構造f[i][j]において、iの要素がf[i][j]の要素とつながっていることを意味する


#f=[list(map(int,input().split())) for _ in range(M)]
#b=[list(map(int,input().split())) for _ in range(K)]
groupid=[0]*N
l=[]
gone=[]
id=1
v=0
v1=0
v2=0
seen=[0]*N
jointelement=[0]*N
jointnum=0
#print(friend,block)
for i in range(N):
    id=i+1
    d=deque()
    if seen[i]==0:
        d.append(i)
    while len(d)>0:
        v=d.popleft()
        seen[v]=1
        groupid[v]=id
        #print(friend[v])
        for i in friend[v]:
            if (seen[i]==0)and(groupid[i]==0):
                d.append(i)
        #print(seen,d,groupid)
c = Counter(groupid)
values = list(c.values())  # aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key = list(c.keys())  # 先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i], values[i]])  # lは[要素i,n_i]の情報を詰めたmatrix
#print(l)
ans=[0]*N
for i in range(N):
    jointnum=c[groupid[i]]
    for j in block[i]:
        if groupid[i]==groupid[j]:
            jointnum=jointnum-1
    ans[i]=jointnum-len(friend[i])-1
print(*ans)






"""なんだこの
while len(f)>0:
    if len(d)==0:
        for i in range(len(gone)):
            groupnum[gone[i]-1]=max(len(gone),groupnum[gone[i]-1])
        gone=[]
        d.append(f[0][0])
    i=0
    v = d.popleft()
    gone.append(v)
    #print(gone)
    while i<len(f):
        if (f[i][0]==v)and(gone.count(f[i][1])==0)and(d.count(f[i][1])==0):
            d.append(f[i][1])
            f.pop(i)
            i=i-1
        elif (f[i][1]==v)and(gone.count(f[i][0])==0)and(d.count(f[i][0])==0):
            d.append(f[i][0])
            f.pop(i)
            i=i-1
        i=i+1
        #print(d,gone)
        #input()
print(groupnum)
for i in range(M):
    groupnum[f2[i][0]-1]=groupnum[f2[i][0]-1]-1
    groupnum[f2[i][1] - 1] = groupnum[f2[i][1] - 1] - 1
for i in range(K):
    groupnum[b2[i][0]-1]=groupnum[b2[i][0]-1]-1
    groupnum[b2[i][1] - 1] = groupnum[b2[i][1] - 1] - 1
for i in range(N):
    groupnum[i]=groupnum[i]-1
print(*groupnum, sep=" ")


for i in range(M):
    v1=f[i][0]
    v2=f[i][1]
    if (groupid[v1-1]==0)and(groupid[])
"""

Submission status: Accepted

Solution code:

def main():
    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()}

    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = UnionFind(n)
    fr = [0]*n

    for i in range(m):
        a,b = map(int,input().split())
        uff.union(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1


    ans = [uff.size(i) -fr[i]-1 for i in range(n)]

    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 1)

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[y] += self.size[x]
            self.p[x] = y
            return True
        else:
            return False

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


n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0] * n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.unite(a,b)
    ans[a] -= 1
    ans[b] -= 1

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
        ans[c] -= 1
        ans[d] -= 1

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

print(' '.join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
#木作って終わり、問題文難しい
#

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m,k = map(int, input().split())
    
    def find(par, x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par, par[x])
            return par[x]
    
    def unite(par, x,y):
        x = find(par,x)
        y = find(par,y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(par, x,y):
        return find(par, x) == find(par, y)
    
    def size(par, x):
        return -par[find(par, x)]

    friend = [-1]*n
    adj = [0]*n
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1] += 1
        adj[b-1] += 1
        unite(friend, a-1, b-1)

    res = []
    for i in range(n):
        p = size(friend, i) - 1 -adj[i]
        res.append(p)

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

    print(*res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#木作って終わり、問題文難しい
#

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m,k = map(int, input().split())
    
    def find(par, x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par, par[x])
            return par[x]
    
    def unite(par, x,y):
        x = find(par,x)
        y = find(par,y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(par, x,y):
        return find(par, x) == find(par, y)
    
    def size(par, x):
        return -par[find(par, x)]

    friend = [-1]*n
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        unite(friend, a-1, b-1)

    res = []
    for i in range(n):
        p = size(friend, i) - 1 -len(adj[i])
        res.append(p)

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

    print(*res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m,k = map(int, input().split())
    
    def find(par, x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par, par[x])
            return par[x]
    
    def unite(par, x,y):
        x = find(par,x)
        y = find(par,y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(par, x,y):
        return find(par, x) == find(par, y)
    
    def size(par, x):
        return -par[find(par, x)]

    def members(par, x, n):
        root = find(par, x)
        return [i for i in range(n) if find(par, i) == root]
    
    friend = [-1]*n
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        unite(friend, a-1, b-1)

    block = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(k):
        a,b = map(int, input().split())
        block[a-1].append(b-1)
        block[b-1].append(a-1)

    res = []
    for i in range(n):
        p = size(friend, i) - 1 -len(adj[i])
        for q in block[i]:
            if same(friend, i, q):
                p -= 1
        res.append(p)
    print(*res)

if __name__ == '__main__':
    main()