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

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]

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)
ans = [0]*n
cnt = [0]*n

for a,b in ab:
    uf.union(a-1, b-1)
    cnt[a-1] += 1
    cnt[b-1] += 1

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

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

for i in range(n):
    print(ans[i] - cnt[i] - 1, end = ' ')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(50000)

def dfs(friends, friend, cluster, visited, belongs, index):
    for i in friends[friend]:
        if not visited[i]:
            visited[i] = True
            cluster.add(i)
            belongs[i] = index
            dfs(friends, i, cluster, visited, belongs, index)

def make_clusters(friends, N):
    clusters = []
    visited = [False] * N
    belongs = [0] * N
    index = 0
    for i in range(N):
        if not visited[i]:
            cluster = set()
            visited[i] = True
            belongs[i] = index
            cluster.add(i)
            dfs(friends, i, cluster, visited, belongs, index)
            index += 1
            clusters.append(cluster)
    return (clusters, belongs)
    
    
N, M, K = map(int, input().split())

friends = [[] for _ in range(N)]
blocks = [set() for _ in range(N)]
clusters = []

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[B].append(A)

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

clusters, belongs = make_clusters(friends, N)

clusters_len = len(clusters)
cluster_len = [0] * clusters_len
for i in range(clusters_len):
    cluster_len[i] = len(clusters[i])

for i in range(N):
    ans = cluster_len[belongs[i]] - len(friends[i]) - len(clusters[belongs[i]] & blocks[i]) - 1
    print(ans, end=' ')

print()

Submission status: Accepted

Solution code:
def find(x):
    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)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)
 
def size(x):
  return-par[find(x)]
 
N,M,K = map(int,input().split())
par=[-1]*N
B = [set() for _ in range(N)]
FF = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
for j in range(K):
    a,b = map(int,input().split())
    B[a-1].add(b-1)
    B[b-1].add(a-1)

Y = []
for i in range(N):
    y = size(i) - FF[i] -1
    for b in B[i]:
        if same(i,b):
            y += -1
    Y.append(str(y))
print(" ".join(Y))

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
some = [1] * N
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
for i in range(K):
    c, d = map(int_, input().split())
    if uf.same(c, d):
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
some = [1] * N
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
for i in range(K):
    c, d = map(int_, input().split())
    if not uf.same(c, d):
        pass
    else:
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

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

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_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)

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


class UnionFind:

    def __init__(self, N):
        self._N = N
        self._parents = [-1 for n in range(N)]
        self._size = [1 for n in range(N)]

    def is_root(self, x):
        return self._parents[x] < 0

    def size(self, x):
        assert self.is_root(x)
        return self._size[x]

    def find(self, x):
        if self.is_root(x):
            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._size[x] > self._size[y]:
            x, y = y, x

        self._parents[y] = x
        self._size[x] += self._size[y]
        self._size[y] = None


def solve():

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

    A = [0 for m in range(M)]
    B = [0 for m in range(M)]
    tree = UnionFind(N)
    for m in range(M):
        A[m], B[m] = map(int, input().split())
        tree.union(A[m]-1, B[m]-1)

    n_friends = [0 for n in range(N)]
    for m in range(M):
        root_a, root_b = tree.find(A[m]-1), tree.find(B[m]-1)
        assert root_a == root_b
        n_friends[A[m]-1] += 1
        n_friends[B[m]-1] += 1

    C = [0 for k in range(K)]
    D = [0 for k in range(K)]
    n_blocks_in_group = [0 for n in range(N)]
    for k in range(K):
        C[k], D[k] = map(int, input().split())
        root_c, root_d = tree.find(C[k]-1), tree.find(D[k]-1)
        if root_c == root_d:
            n_blocks_in_group[C[k]-1] += 1
            n_blocks_in_group[D[k]-1] += 1

    res = []
    for n in range(N):
        n_cand = tree.size(tree.find(n)) - n_friends[n] - n_blocks_in_group[n] - 1
        res.append(str(n_cand))
    print(' '.join(res))


solve()

Submission status: Accepted

Solution code:
def find(x):
    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)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)

def size(x):
  return-par[find(x)]
  
n,m,k=map(int,input().split())

par=[-1]*n

F=[]
B=[]

f=[set() for _ in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    F.append([a,b])
    
for i in range(k):
    c,d=map(int,input().split())
    B.append([c,d])

for a,b in F:
    a-=1
    b-=1
    unite(a,b)
    f[a].add(b)
    f[b].add(a)

a=[size(i)-len(f[i])-1 for i in range(n)]

for c,d in B:
    c-=1
    d-=1
    if same(c,d):
        a[c]-=1
        a[d]-=1
print(*a)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)


N, M, K = map(int, input().split())
F = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
B = [list(map(lambda x:int(x)-1, input().split())) for _ in range(K)]

B_set = [set() for _ in range(N)]
F_set = [set() for _ in range(N)]
for a, b in B:
    B_set[a].add(b)
    B_set[b].add(a)
for a, b in F:
    F_set[a].add(b)
    F_set[b].add(a)

Un = UnionFind(N)
for a, b in F:
    Un.union(a, b)

ans = [0]*N
for i in range(N):
    in_group_B = 0
    for b in B_set[i]:
        if Un.same(b, i):
            in_group_B += 1
    ans[i] = Un.connectedNum(i) - len(F_set[i])-in_group_B-1
print(*ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    """ Union-Find木の実装（ランクあり） """
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    # parent 親 マイナスだったら根で、絶対値が集合の数
        self.rank   = [0]*(n+1)     # rank 深さ

    def root(self, x):
        """ 木の根を求める """
        if self.parent[x] < 0:      # xが根
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  # 経路圧縮
            return self.parent[x]
            
    def unite(self, x, y):
        """ xとyの属する集合を併合 """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.root(x) == self.root(y) or x==y
    
    def size(self, x):
        """ xと同じ集合に属する数 """
        return -self.parent[self.root(x)]


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1; B -= 1
    uf.unite(A, B)
    friends[A].append(B)
    friends[B].append(A)
for i in range(K):
    C, D = map(int, input().split())
    C -= 1; D -= 1
    blocks[C].append(D)
    blocks[D].append(C)

ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - 1   # 自分を除外
    ans[i] -= len(friends[i]) # 既に友達を除外
    block_num = 0
    for j in blocks[i]:
        if uf.isSame(i,j):
            block_num += 1
    ans[i] -= block_num

print(*ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, N):
        self.roots = list(range(N + 1))
        self.counter = [1] * (N + 1)

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

def resolve():
    N, M, K = [int(x) for x in input().split()]
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    uf = UnionFind(N)

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)
        uf.union(A,B)

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

    for i in range(N):
        ans = uf.count(i) - len(list[i]) - 1
        for j in block[i]:
            if uf.find(i ,j):
                ans -= 1

        print(ans, end=" ")

resolve()

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():
    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 = self.Find_Root(x)
        y = 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 isSameGroup(self,x,y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

ans = [-1] * (N+1)
for i in range(M):
    a,b = map(int,input().split())
    ans[a] -= 1
    ans[b] -= 1
    t.Unite(a,b)

for i in range(N):
    ans[i+1] += t.Count(i+1)

for i in range(K):
    c,d = map(int,input().split())
    if t.isSameGroup(c,d):
        ans[c] -= 1
        ans[d] -= 1

del ans[0]
print(' '.join(map(str,ans)))

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 = self.Find_Root(x)
        y = 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 isSameGroup(self,x,y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

friends = [0] * (N+1)
for i in range(M):
    a,b = map(int,input().split())
    friends[a] += 1
    friends[b] += 1
    t.Unite(a,b)

ans = [t.Count(i+1) - friends[i+1] - 1 for i in range(N)]

block = [0] * (N+1)
for i in range(K):
    c,d = map(int,input().split())
    if t.isSameGroup(c,d):
        ans[c-1] -= 1
        ans[d-1] -= 1

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        # 子：親のid
        # 親：-サイズ（<0）
        self.d = [-1] * n
    
    # xの親を探す
    def find(self, x):
        if(self.d[x] < 0):
            # x自身が親
            return x
        else:
            # 親のidを格納
            self.d[x] = self.find(self.d[x])
            return self.d[x]
        
    # x,yを結合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x!=y):
            # yの方がサイズが大きい場合
            if(self.d[x] > self.d[y]):
                # サイズの結合・親のidの格納
                self.d[y] += self.d[x]
                self.d[x] = y
            else:
                self.d[x] += self.d[y]
                self.d[y] = x
    
    # 連結成分のサイズを返す
    def size(self, x):
        if(self.d[x] < 0):
            return -self.d[x]
        else:
            return -self.d[self.find(x)]
    
    # 親が同じならTrue
    def same(self,x,y):
        return (self.find(x) == self.find(y))


N, M, K = map(int, input().split())
ut_f = UnionFind(N)
ut_b = UnionFind(N)
ab = []
cd = [] 
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ut_f.unite(a,b)
    ab.append((a,b))
for j in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    ut_b.unite(c,d)
    cd.append((c,d))

ans = [0] * N
for i in range(N):
    ans[i] = ut_f.size(i) - 1

# 友達を引く
for a,b in ab:
    if(ut_f.same(a,b)):
        ans[a] -= 1
        ans[b] -= 1

# ブロック関係を引く
for c,d in cd:
    # 友達に関する同じ連結成分内だったら、友達候補から外す
    if(ut_f.same(c,d)):
        ans[c] -= 1
        ans[d] -= 1
print(*ans)

Submission status: Accepted

Solution code:
N, M, K=map(int, input().split())

#友達候補：　ブロック関係にない　友達ではない　間接的に友達
#友達候補＝友達の輪　ー　友達
#ブロックリストが友達の輪とsamegroupだったら−１

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を見てくっつける方を決める
      #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)]
  
uni=UnionFind(N)
friends=[[] for _ in range(N)]
blocks=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int, input().split())
  friends[a-1].append(b-1)
  friends[b-1].append(a-1)
  uni.Unite(a-1,b-1)
for i in range(K):
  c,d=map(int, input().split())
  blocks[c-1].append(d-1)
  blocks[d-1].append(c-1)
  
for i in range(N):
  ans=uni.Count(i)-len(friends[i])-1
  for j in blocks[i]:
    if uni.isSameGroup(i,j):
      ans-=1
  print(ans, end=" ")

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self,n):
        self.n=n
        self.par=[-1]*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):
        rx=self.root(x)
        ry=self.root(y)
        if rx==ry:
            return
        if self.par[rx]>self.par[ry]:
            rx,ry=ry,rx
        self.par[rx]+=self.par[ry]
        self.par[ry]=rx

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

    def same(self,x,y):
        return self.root(x)==self.root(y)
N,M,K=map(int,input().split())
deg=[0]*N
bro=[[]*N for _ in range(N)]
uf=Union_Find(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    deg[a]+=1
    deg[b]+=1
    uf.union(a,b)
for j in range(K):
    a,b=map(int,input().split())
    a-=1
    b-=1
    bro[a].append(b)
    bro[b].append(a)

for q in range(N):
    ans=uf.size(q)-deg[q]-1
    for w in bro[q]:
        if uf.same(q,w):
            ans-=1
    print(ans,end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.volume > taroot.volume:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

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

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

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

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)