Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:

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

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

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

        if(self.parents[x] > self.parents[y]):
            x,y = y,x        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def count(self,x):
        return -self.parents[self.find(x)]

    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 __str__(self):
        return '\n'.join('{}: {}'.format(root, self.members(root)) for root in self.roots())

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

uf_friend = UnionFind(n+1)
uf_block = UnionFind(n+1)
count = [0]*(n+1)
for i in range(m):
    a,b = map(int, input().split(" "))
    uf_friend.union(a, b)
    count[a] += 1
    count[b] += 1

for i in range(k):
    a,b = map(int, input().split(" "))
    if(uf_friend.issame(a,b)):
        count[a] += 1
        count[b] += 1

result = [0]*n
for i in range(1,n+1):
    result[i-1] = uf_friend.count(i) - count[i] - 1

print(*result)

Submission status: Accepted

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


from collections import defaultdict


def main():
    n, m, k = map(int, input().split())
    fr_ed_c = defaultdict(int)  # node -> count

    parents = {}  # node -> parent_node
    root_2_nc = {}  # node -> count

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

        p_a = get_root(parents, a)
        p_b = get_root(parents, b)

        if p_a == p_b:
            # already same cluster. do nothing.
            pass
        else:
            # cluster integration
            p_a_c = root_2_nc.get(p_a, 1)
            p_b_c = root_2_nc.get(p_b, 1)
            p_a, p_b = (p_a, p_b) if p_a_c < p_b_c else (p_b, p_a)
            parents[p_a] = p_b
            if p_b not in root_2_nc:
                root_2_nc[p_b] = 1
            root_2_nc[p_b] += root_2_nc.pop(p_a, 1)

    br_ed = defaultdict(set)  # node -> set()
    for i in range(k):
        c, d = map(int, input().split())
        br_ed[c].add(d)
        br_ed[d].add(c)

    ans_list = []
    for i_m in range(n):
        i = i_m + 1
        root = get_root(parents, i)
        block_count = 0
        for b in br_ed[i]:
            b_root = get_root(parents, b)
            block_count += 1 if root == b_root else 0
        ans = root_2_nc.get(root, 1) - 1 - fr_ed_c.get(i, 0) - block_count
        ans_list.append(str(ans))
    print(" ".join(ans_list))


def get_root(parents, i):
    if i not in parents:
        return i
    return get_root(parents, parents[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60

#Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ここから書き始める
n, m, k = map(int, input().split())
uf = UnionFind(n)
dame = [set() for i in range(n)]
# print(uf)

# print(direct)
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k
for i in range(m + k):
    x, y = map(int, input().split())
    if i < m:
        a[i] = x - 1
        b[i] = y - 1
        uf.union(x - 1, y - 1)
    else:
        c[i - m] = x - 1
        d[i - m] = y - 1
e = [set() for i in range(n)]
for i in range(m):
    if uf.same(a[i], b[i]):
        e[a[i]].add(b[i])
        e[b[i]].add(a[i])
for i in range(k):
    # if c[i] == 6 and d[i] == 4:
    #     # print(uf.same(c[i], d[i]))
    if uf.same(c[i], d[i]):
        e[c[i]].add(d[i])
        e[d[i]].add(c[i])
# print(e)
# print(uf)
for i in range(n):
    print("%d " % (uf.size(i) - len(e[i]) - 1), end="")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n+1))
        self.size = [1] * (n+1)
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if self.parent[a] == self.parent[b]:
            return
        if self.size[a] >= self.size[b]:
            self.parent[b] = a
            self.size[a] += self.size[b]
        else:
            self.parent[a] = b
            self.size[b] += self.size[a]
        
    def is_same(self, a, b):
        return self.find(a) == self.find(b)
    
    def count(self, x):        
        return self.size[self.find(x)]

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

uf = UnionFind(n)
ans = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for _ in range(k):
    a, b = map(int, input().split())
    if uf.is_same(a, b):
        ans[a] -= 1
        ans[b] -= 1
        
for i in range(1, n+1):
    ans[i] += uf.count(i) - 1    
    
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n+1))
        self.size = [1] * (n+1)
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if self.parent[a] == self.parent[b]:
            return
        if self.size[a] >= self.size[b]:
            self.parent[b] = a
            self.size[a] += self.size[b]
        else:
            self.parent[a] = b
            self.size[b] += self.size[a]
        
    def count(self, x):        
        return self.size[self.find(x)]

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

uf = UnionFind(n)
ans = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for _ in range(k):
    a, b = map(int, input().split())
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1
        
for i in range(1, n+1):
    ans[i] += uf.count(i) - 1    
    
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N, l):
        self.roots = list(range(N+1))
        self.counter = [1]*(N+1)
        for a, b in l:
            self.union(a, b)

    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]

    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0

    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)

    def count(self, x):
        return(self.counter[self.get_root(x)])


N, M, K = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(M)]
cd = [[int(i) for i in input().split()] for _ in range(K)]
friend = [[] for _ in range(N+1)]
uf = UnionFind(N, ab)

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

ans = [uf.count(i)-1-len(friend[i]) for i in range(N+1)]

for c, d in cd:
    if uf.find(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_size", "_first_idx", "_parents"]

    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)

    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]
n,m,k=map(int,input().split())
from sys import stdin 
input=stdin.readline
friend=[0]*(n+1)
uf=UnionFind(n,1)
for i in range(m):
    a,s=map(int,input().split())
    uf.unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    anti[a].add(b)
    anti[b].add(a)
print(*[uf.size(i)-1-sum(uf.same(i,b) for b in anti[i])-friend[i] for i in range(1,n+1)],sep=" ")

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    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 size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)
from sys import stdin 
input=stdin.readline
friend=[0]*n
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)

print(*[size(i)-1-sum(same(i,b) for b in anti[i])-friend[i] for i in range(n)],sep=" ")

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

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return
        if self.rank[x] <self.rank[y]:
            self.par[y] += self.par[x] #負+負でsize管理 
            self.par[x] = y
        else:
            self.par[x] += self.par[y]
            self.par[y] = x
            if self.rank[x] == self.rank[y]: #負+負でsize管理 
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

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

friend = [[]*(n+1) for i in range(n+1)]
for i in range(m):
    friend[a[i]].append(b[i])

block = [[]*(n+1) for i in range(n+1)]
for i in range(k):
    block[c[i]].append(d[i])
    block[d[i]].append(c[i])

Tree = UnionFind(n)

for i in range(1,len(friend)):
    for j in friend[i]:
        Tree.union(i-1,j-1)

for i in range(m):
    friend[b[i]].append(a[i])

ans = [0]*n

for i in range(n):
    s = Tree.size(i)
    s -= len(friend[i+1]) #既に友達
    for j in block[i+1]:
        if Tree.is_same(i,j-1): #ブロックされてる
            s -= 1

    ans[i] = s-1

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, k = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)

        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

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

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)
ab = []
cd = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    cd.append((c, d))

ans = [uf.count_member(i)-1 for i in range(n)]

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

for c, d in cd:
    if uf.same(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, k = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)

        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

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

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)
ab = []
cd = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    cd.append((c, d))

ans = [uf.count_member(i)-1 for i in range(n)]

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

for c, d in cd:
    if uf.same(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

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

n,m,k=map(int,input().split())
uf=UF(n)
F=[set()for _ in range(n)]
B=[0]*n
for i in range(m):
      a,b=map(int,input().split())
      uf.union(a-1,b-1)
      F[a-1].add(b-1)
      F[b-1].add(a-1)
for i in range(k):
      c,d=map(int,input().split())
      if uf.same(c-1,d-1):
            B[c-1]-=1
            B[d-1]-=1
L=[]
for i in range(n):
      L.append(uf.size(i)-1-len(F[i])+B[i])
print(*L)

Submission status: Accepted

Solution code:
class UnionFind():
 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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x, y = self.find_root(x), self.find_root(y)
        if(x == y):
            return
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
    def __str__(self):
        return 'UnionFind(n: {}, root: {}, rnk: {})'.format(self.n, self.root, self.rnk)
    
    def __repr__(self):
        return self.__str__()

inputs = open(0).readlines()
n, m, k = map(int, inputs[0].split())
AB = [tuple(map(int, ab.split())) for ab in inputs[1:m+1]]
CD = [tuple(map(int, cd.split())) for cd in inputs[m+1:]]

uf = UnionFind(n)
friends = [set() for _ in range(n)]
for n0, n1 in AB:
    uf.unite(n0-1, n1-1)
    friends[n0-1].add(n1-1)
    friends[n1-1].add(n0-1)

blocks = [set() for _ in range(n)]
for n0, n1 in CD:
    if uf.is_same_group(n0-1, n1-1):
        blocks[n0-1].add(n1-1)
        blocks[n1-1].add(n0-1)

candidates = []
for i in range(n):
    candidates.append(uf.count(i) - len(friends[i]) - len(blocks[i]) - 1)
print(*candidates)

Submission status: Accepted

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


n,m,k=map(int,input().split())
F=[set()for _ in range(n)]
uf=UF(n)
for i in range(m):
      a,b=map(int,input().split())
      uf.union(a-1,b-1)
      F[a-1].add(b-1)
      F[b-1].add(a-1)
B=[0]*n
for i in range(k):
      c,d=map(int,input().split())
      if uf.same(c-1,d-1):
            B[c-1]-=1
            B[d-1]-=1
ans=[]
for i in range(n):
      ans.append(uf.size(i)+B[i]-1-len(F[i]))
print(*ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if uf.same(c, d):
        block[c].append(d)
        block[d].append(c)
ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.par = []
        self.size = []
        for i in range(n):
            self.par.append(i)
            self.size.append(1)

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) #recurcive
            return self.par[x]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.par[y] = x
        self.size[x] += self.size[y]

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

n,m,k = map(int, input().split())
uf = UnionFind(n)
non = [set() for _ in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    uf.unite(a-1,b-1) # a&b is friends
    non[a-1].add(b-1)
    non[b-1].add(a-1)

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

answer = []
for i in range(n):
    ans = uf.root_size(i)-len(non[i])-1
    answer.append(ans)

print(*answer)

Submission status: Accepted

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

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

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 same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

uf = UnionFind(n)
friend =[[] for _ in range(n)]
block = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    uf.union(a,b)
    friend[a].append(b); friend[b].append(a)

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

w = [0] * n
for i in range(n):
    w[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1

print(*w)

Submission status: Accepted

Solution code:
# import bisect
# # import heapq
# # from copy import deepcopy
from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math

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

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 same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

uf = UnionFind(n)
friend =[[] for _ in range(n)]
block = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    uf.union(a,b)
    friend[a].append(b); friend[b].append(a)

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

w = [0] * n
for i in range(n):
    w[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1

print(*w)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections


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

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

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

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

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

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


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

friend_cnt = [0] * n
blocked_cnt = [0] * n

uf = UnionFind(n)

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

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

for i in range(n):
    renketsu_cnt_i = uf.Count(i)
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - friend_cnt[i] - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()