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:
def main():
    n, m, k = map(int, input().split())
    fb = [0]*(n+1)
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        fb[a] += 1
        fb[b] += 1
        uf.unite(a, b)
    for i in range(k):
        c, d = map(int, input().split())
        # 友達の輪の中にいたら
        if uf.same(c, d):
            fb[c] += 1
            fb[d] += 1
    ans = [uf.size(i)-1-fb[i] for i in range(1, n+1)]
    print(" ".join(list(map(str, ans))))


class UnionFind:
    __slots__ = ["data"]
    
    def __init__(self, n=0):
        self.data = [-1]*(n+1)
    
    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.data[x] < self.data[y]:
                self.data[x] += self.data[y]
                self.data[y] = x
            else:
                self.data[y] += self.data[x]
                self.data[x] = y
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.data[self.root(x)]



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()
n, m, k = map(int, input().split())

fgraph = [list() for _ in range(n)]  # 隣接行列のリスト版
bgraph = [list() for _ in range(n)]  # brock関係のグラフ
cgraph = [list() for _ in range(n)]  # 友達候補のグラフ
sys.setrecursionlimit(10**9)
rks = [None]*n


def dfs(graph, s, r):  # 深さ優先探索
    if rks[s] is None:
        rks[s] = r
    for j in range(len(graph[s])):
        if rks[graph[s][j] - 1] is not None:
            continue
        dfs(graph, graph[s][j]-1, r)


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

 # fgraphの連結成分を調べる
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)  # iから始めるDFS。ｃが同じなら同じ連結成分にいる

for i in range(k):
    c, d = map(int, input().split())
    if rks[c-1] == rks[d-1]:  # 同一連結成分の中でのブロック関係のみ注目
        bgraph[c-1].append(d)
        bgraph[d-1].append(c)

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Accepted

Solution code:
from collections import deque
n,m,k = map(int,input().split())
friend = [set() for i in range(n)]
block = [set() for i in range(n)]

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

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

for i in range(n):
    if visited[i]:continue
    now = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        num = stack.pop()
        for j in friend[num]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                now.add(j)
    for i in now:
        ans[i] = len(now)-len(now&friend[i])-len(now&block[i])-1
for answer in ans:
    print(answer,end=" ")

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())
num_fri = [0] * N
union = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    num_fri[a] += 1
    num_fri[b] += 1
    union.union(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if union.same(a, b):
        num_fri[a] += 1
        num_fri[b] += 1
for i in range(N):
    print(union.size(i) - 1 - num_fri[i], end=' ')

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
check = [0]*n
union = [-1]*n
union[0] = 0
for i in range(n):
    if check[i]: continue
    que = deque([i])
    while que:
        u = que.popleft()
        for v in friend[u]:
            if check[v]: continue
            union[v] = i
            check[v] = 1
            que.append(v)
            
brock = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    if union[c-1] == union[d-1]:
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
ans = [0]*n
check = [0]*n
for i in range(n):
    if check[i] or union[i]==-1: continue
    que = deque([i])
    for j in range(i+1, n):
        if union[j] == union[i]: que.append(j)
    res = len(que)
    while que:
        u = que.popleft()
        check[u] = 1
        ans[u] = res-len(friend[u])-len(brock[u])-1
print(*ans)

Submission status: Accepted

Solution code:
# Problem D - Friend Suggestions

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())

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

# initialization
friend_uf = UnionFind(N)
not_list = [[] for i in range(N+1)]
ans_list = [0] * (N)

# friend relation union
for i in range(M):
    a, b = map(int, input().split())
    friend_uf.union(a-1, b-1)
    not_list[a].append(b)
    not_list[b].append(a)

# block relation union
for i in range(K):
    c, d = map(int, input().split())
    if friend_uf.same(c-1, d-1):
        not_list[c].append(d)
        not_list[d].append(c)

# output
for i in range(1, N+1):
    group_size = friend_uf.size(i-1)
    not_size = not_list[i]
    ans = group_size - len(set(not_size)) - 1
    ans_list[i-1] = ans
ans_list = list(map(str, ans_list))
print(" ".join(ans_list))

Submission status: Accepted

Solution code:
import sys


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

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

    def size(self, x):
        return -self.d[self.root(x)]


input = sys.stdin.readline
N, M, K = map(int, input().split())
F = [[] for _ in [0]*N]
B = [[] for _ in [0]*N]

uf = UnionFind(N)

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

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

for i in range(N):
    ans = uf.size(i) - 1
    ans -= len(F[i])
    for b in B[i]:
        if uf.same(i, b):
            ans -= 1
    print(ans, end=' ')

Submission status: Accepted

Solution code:
#id:KabukiMining
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#@YottyPG　Qiita
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

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 f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Accepted

Solution code:
#あっとのTECH LOG
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.union(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block):
            ans[iam] -= 1

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
#ika tako
import sys 
 
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def count(self, x):
        return -self.table[self._root(x)]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

n, m, k = map(int, sys.stdin.buffer.readline().split())
abcd = list(map(int, sys.stdin.buffer.read().split()))
uft = UnionFind(n)
friends = [0 for _ in range(n)]
blocks = [set() for _ in range(n)]
for a, b in zip(abcd[0:2 * m:2], abcd[1:2 * m:2]):
    a -= 1
    b -= 1
    uft.union(a, b)
    friends[a] += 1
    friends[b] += 1
for c, d in zip(abcd[2 * m::2], abcd[2 * m + 1::2]):
    c -= 1
    d -= 1
    blocks[c].add(d)
    blocks[d].add(c)
ans = []
for i in range(n):
    ans.append(uft.count(i) - 1 - friends[i] - sum(uft.find(i, j) for j in blocks[i]))
print(*ans)

Submission status: Accepted

Solution code:
#Satoooh blog
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる
C, D = [0] * K, [0] * K  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(direct[i]) - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():#たのんnote
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])

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())

d = UnionFind(N)
num_fri = [0] * N
for i in range(M):
    a, b = map(int, input().split())
    d.union(a - 1, b - 1)
    num_fri[a - 1] += 1
    num_fri[b - 1] += 1
#num = [d.size(i) for i in range(N)]
for i in range(K):
    a, b = map(int, input().split())
    if d.same(a - 1, b - 1):
        num_fri[a - 1] += 1
        num_fri[b - 1] += 1
for i in range(N):
    print((d.size(i) - 1) - num_fri[i], end=' ')

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
par = [i for i in range(n)]
rank = [1] * n
fr = [[] for i in range(n)]
br = [[] for i in range(n)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])  # 経路圧縮
        return par[x]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        rank[y] += rank[x]
        par[x] = y
    else:
        rank[x] += rank[y]
        par[y] = x

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

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

res = []
for i in range(n):
    cnt = 0
    if br[i]:
        for b in br[i]:
            if same(i, find(b)):
                cnt += 1
        res.append(rank[find(i)] - len(fr[i]) - cnt - 1)
    else:
        res.append(rank[find(i)] - len(fr[i]) - 1)
print(*res, sep=" ")

Submission status: Accepted

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


class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

    def ifSame(self, x, y):
        return self.root(x) == self.root(y)

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


N, M, K = map(int, input().split())
friend_tree = UnionFind(N)
like_array = [[] for _ in range(N)]
for _ in range(M):
    # 友人木を構築する
    A, B = map(int, input().split())
    like_array[B-1].append(A-1)
    like_array[A-1].append(B-1)
    if not friend_tree.ifSame(A-1, B-1):
        friend_tree.unite(A-1, B-1)

# friend_tree.printDebugInfo()

friend_groups = {}
for i in range(N):
    root = friend_tree.root(i)
    if root in friend_groups.keys():
        friend_groups[root] += 1
    else:
        friend_groups[root] = 1

# print(friend_groups)

dislike_array = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(int, input().split())
    dislike_array[C-1].append(D-1)
    dislike_array[D-1].append(C-1)

# print(dislike_array)

answer = []
for i in range(N):
    root = friend_tree.root(i)
    friends_count = friend_groups[root] - 1

    blockd_friend = 0
    for dislike_person in dislike_array[i]:
        if friend_tree.ifSame(i, dislike_person):
            blockd_friend += 1

    kai = friends_count - blockd_friend - len(like_array[i])
    answer.append(str(kai))

print(" ".join(answer))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

def search(i, fc):
    cur = i
    while fc[cur] != cur:
        cur = fc[cur]

    #fc[i] = cur
    return cur

def union(i, j, fc, fcn):
    if fcn[i] > fcn[j]:
        fc[j] = i
        fcn[i] += fcn[j]
    else:
        fc[i] = j
        fcn[j] += fcn[i]
        

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

dfn = [ 0 for i in range(n + 1) ]
tbn = [ 0 for i in range(n + 1) ]
fc = [ i for i in range(n + 1) ]
fcn = [ 1 for i in range(n + 1) ]

for i in range(m):
    (a, b) = map(int, input().split())
    dfn[a] += 1
    dfn[b] += 1
    ag = search(a, fc)
    bg = search(b, fc)
    if ag != bg:
        union(ag, bg, fc, fcn)

for i in range(k):
    (c, d) = map(int, input().split())
    if search(c, fc) == search(d, fc):
        tbn[c] += 1
        tbn[d] += 1

#print('fc', fc)
#print('fcn', fcn)
#print('dfn', dfn)
#print('tbn', tbn)
        
print(' '.join((str(fcn[search(i, fc)] - dfn[i] - tbn[i] - 1) for i in range(1, n + 1))))

Submission status: Accepted

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

l=list(range(N+1))
r=[0]*(N+1)
size=[1]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
        size[X]+=size[Y]
    else:
        l[X]=l[Y]

        if r[X]==r[Y]:
            r[Y]+=1
        if X!=Y:
            size[Y] += size[X]
for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

t=[]
for i in range(N+1):
    p=size[find(i)]-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

def dec(n):
    return n-1


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

u = UnionFind(n)


for i in range(m):
    a,b = map(dec,map(int, input().split()))
    u.unite(a,b)
    block[a].append(b)
    block[b].append(a)

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

ans_all = []
for i in range(n):
    ans = u.size(i)-1
    for x in block[i]:
        if u.same(i,x):
            ans-=1
    ans_all.append(ans)

print(' '.join(map(str,ans_all)))

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(1000000000)

class union_find:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.excluded = [0 for i in range(N)]
    
    def root(self, a):
        if self.par[a] == a:
            return a
        else:
            # 経路圧縮
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.size[self.root(b)] += self.get_union_size(a)
            self.par[self.root(a)] = self.root(b)
    
    def friend(self, a, b):
        self.unite(a, b)
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def block(self, a, b):
        if self.same(a, b):
            self.excluded[a] += 1
            self.excluded[b] += 1

    def get_union_size(self, a):
        return self.size[self.root(a)]
    
    def get_friend_sugestion_size(self, a):
        return self.get_union_size(a) - 1 - self.excluded[a]

N, M, K = map(int, input().split())
UF = union_find(N)
for i in range(M):
    A, B = map(int, input().split())
    UF.friend(A-1, B-1)
for i in range(K):
    A, B = map(int, input().split())
    UF.block(A-1, B-1)
print(*[UF.get_friend_sugestion_size(x) for x in range(N)])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
ab = [list(map(int, readline().split())) for _ in range(m)]
cd = [list(map(int, readline().split())) for _ in range(k)]
uf_p = UnionFind(n + 1)
for a, b in ab:
    uf_p.union(a, b)
ans = [uf_p.size(i) - 1 for i in range(1, n + 1)]
for a, b in ab:
    ans[a - 1] -= 1
    ans[b - 1] -= 1
for c, d in cd:
    if uf_p.same(c, d):
        ans[c - 1] -= 1
        ans[d - 1] -= 1
print(*ans)