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():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    edge = [set() for _ in range(N)]
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        edge[a-1].add(b-1)
        edge[b-1].add(a-1)
        unite(a-1, b-1)
    from collections import Counter
    for i, x in enumerate(par):
        unite(i, x)
    c = Counter(par)  # 頂点iの連結成分のサイズ
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            edge[a-1].add(b-1)
            edge[b-1].add(a-1)
    for i in range(N):
        cur = c[par[i]] - len(edge[i]) - 1
        print(cur, end=" ")
    print()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

NIL = -1
N, M, K = map(int, input().split())
relation = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

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

def dfs(x, y):
    for i in relation[y]:
        if check[i] == None:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = x
            dfs(x, i)

#print(prefriends)
j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        #print(prefriends[j])
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        #print(check)
    j += 1
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if check[C] == check[D]:
        relation[C].append(D)
        relation[D].append(C)
ans = [0]*N
for j in range(N):
    ans[j] = len(prefriends[check[j]]) - len(relation[j]) - 1
    #print(ans[j])
    #print()
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

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

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[x]<size[y]: x,y=y,x  #xの要素数が大きいように
    size[x]+=size[y]
    par[y]=x


def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
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())
uni = UnionFind(N)
fn = [0 for i in range(N)]
bl = [[] for i in range(N)]
bn = [0 for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    fn[a] +=1
    fn[b] += 1
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    if uni.find(a) == uni.find(b):
        bn[a] += 1
        bn[b] += 1
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = uni.size(i) - bn[i] - fn[i] -1
print(' '.join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, 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

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

uf = UnionFind(N)
friend_suggested = [-1] * N


for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friend_suggested[a] -= 1
    friend_suggested[b] -= 1
    uf.union(a, b)
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.find(c) == uf.find(d):
        friend_suggested[c] -= 1
        friend_suggested[d] -= 1

for i in range(N):
    parent_size = -uf.parents[uf.find(i)]
    friend_suggested[i] += parent_size
print(*friend_suggested)

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


from collections import defaultdict
 
n, m, k = map(int, input().split())
uf = UnionFind(n+1)
friends = defaultdict(int)
block = defaultdict(int)

# Union-Find木を構築する+各人の直接の友達の数を数える
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    friends[a] += 1
    friends[b] += 1

# Union-Find構造で同じグループに属している(友達の友達or友達の友達の友達or...)場合は、
# ブロック候補として数える(同じグループでない場合は、そもそも友達候補ではない)
for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        block[c] += 1
        block[d] += 1

# 同じグループの人数から、直接の友達の数、ブロック候補の数(別グループの人は含まない)、
# そして、自分の分を差し引けば、友達候補の数を求められる
ans = []
for i in range(1, n+1):
    group_sise = uf.size(i)
    friend_size = friends[i]
    block_size = block[i]
    ans.append(group_sise - friend_size - block_size - 1)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    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)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)


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

uf = UnionFind(n)

for a, b in ab:
    a -= 1
    b -= 1
    uf.unite(a, b)

uf.update_p()

counter = Counter(uf.p)

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


def f(li):
    for e1, e2 in li:
        e1 -= 1
        e2 -= 1
        if uf.same(e1, e2):
            ans[e1] -= 1
            ans[e2] -= 1


f(ab)
f(cd)

print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1


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

uf = UnionFind(n)

for a, b in ab:
    a -= 1
    b -= 1
    uf.unite(a, b)

for i in range(n):
    uf.find_set(i)

counter = Counter(uf.p)

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


def f(li):
    for e1, e2 in li:
        e1 -= 1
        e2 -= 1
        if uf.same(e1, e2):
            ans[e1] -= 1
            ans[e2] -= 1


f(ab)
f(cd)

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 = [set() for _ in range(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)
        if not self.group[root]:
            for i in range(self.n):
                if self.find(i) == root:
                    self.group[root].add(i)
        return self.group[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 main():
    N, M, K = map(int, input().split())
    uni = UnionFind(N)
    not_cand = [0] * N
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        not_cand[A] += 1
        not_cand[B] += 1
        uni.union(A,B)
 
    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        if uni.same(C,D):
            not_cand[C] += 1
            not_cand[D] += 1
            
    
    ans = [0] * N
    for i in range(N):
        ans[i] = uni.size(i) - not_cand[i] - 1
    
    print(*ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
w=[i for i in range(n+1)]
s=[1]*(n+1)
g=[list(map(int,input().split()))for i in range(m)]
def root(x):
    if w[x]==x:
        return x
    x=w[x]
    return root(w[x])
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if s[x]<s[y]:
            w[x]=y
            s[y]+=s[x]
        else:
            w[y]=x
            s[x]+=s[y]
for i in range(m):
    a,b=g[i][0],g[i][1]
    unite(a,b)
for i in range(1,n+1):
    w[i]=root(i)
    s[i]=s[w[i]]
for i in range(m):
    s[g[i][0]]-=1
    s[g[i][1]]-=1
for i in range(k):
    a,b=map(int,input().split())
    if w[a]==w[b]:
        s[a]-=1
        s[b]-=1
for i in range(1,n+1):s[i]-=1
print(*s[1:])

Submission status: Accepted

Solution code:
# D - Friend Suggestions
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:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        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 get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]


def main():
    N, M, K, *ABCD = map(int, open(0).read().split())
    AB, CD = ABCD[:2 * M], ABCD[2 * M:]
    relationships = UnionFind(N, 1)
    non_candidates = [1] * (N + 1)  # Friends, mutually blocked persons, and user themselves can't be candidates.
    for a, b in zip(*[iter(AB)] * 2):
        relationships.unite(a, b)
        non_candidates[a] += 1
        non_candidates[b] += 1
    for c, d in zip(*[iter(CD)] * 2):
        if relationships.is_same(c, d):
            non_candidates[c] += 1
            non_candidates[d] += 1
    ans = [relationships.get_size(i) - non_candidates[i] for i in range(1, N + 1)]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Friend Suggestions
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:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        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 get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]


def main():
    N, M, K, *ABCD = map(int, open(0).read().split())
    AB, CD = ABCD[:2 * M], ABCD[2 * M:]
    relationships = UnionFind(N, 1)
    friends, blocked = [0] * (N + 1), [0] * (N + 1)
    for a, b in zip(*[iter(AB)] * 2):
        relationships.unite(a, b)
        friends[a] += 1
        friends[b] += 1
    for c, d in zip(*[iter(CD)] * 2):
        if relationships.is_same(c, d):
            blocked[c] += 1
            blocked[d] += 1
    ans = [relationships.get_size(i) - friends[i] - blocked[i] - 1 for i in range(1, N + 1)]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D 解き直し
# 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())
not_ans = [1 for i in range(n)]
ans = [0 for i in range(n)]
unions = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    not_ans[a-1] += 1
    not_ans[b-1] += 1
    unions.union(a-1, b-1)
for i in range(k):
    a,b = map(int, input().split())
    if unions.same(a-1, b-1):
        not_ans[a-1] += 1
        not_ans[b-1] += 1
for i in range(n):
    ans[i] = unions.size(i) - not_ans[i]
print(*ans)

Submission status: Accepted

Solution code:
def root(x):
  while par[x]>=0:x=par[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x!=y:
    if x>y:x,y=y,x
    par[x]+=par[y]
    par[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return-par[root(x)]
n,m,k,*t=map(int,open(0).read().split())
par=[-1]*n
f=[set()for _ in range(n)]
for a,b in zip(*[iter(t[:m*2])]*2):
  a-=1
  b-=1
  unite(a,b)
  f[a].add(b)
  f[b].add(a)
a=[size(i)-len(f[i])-1for i in range(n)]
for c,d in zip(*[iter(t[m*2:])]*2):
  c-=1
  d-=1
  if same(c,d):
    a[c]-=1
    a[d]-=1
print(*a)

Submission status: Accepted

Solution code:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
#import collections
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, m, k = list(map(int,ipti().split()))
    r = UnionFind(n)
    rr = [0] * n
    fr = [[0] * 2 for _ in range(m)]
    bl = [[0] * 2 for _ in range(k)]

    for i in range(m):
        a, b = list(map(int,ipti().split()))
        fr[i][0] = a - 1
        fr[i][1] = b - 1
        r.union(fr[i][0], fr[i][1])

    for i in range(k):
        a, b = list(map(int,ipti().split()))
        bl[i][0] = a - 1
        bl[i][1] = b - 1

    for i in range(m):
        a, b = fr[i][0], fr[i][1]
        if r.same(a, b):
            rr[a] += 1
            rr[b] += 1

    for i in range(k):
        a, b = bl[i][0], bl[i][1]
        if r.same(a, b):
            rr[a] += 1
            rr[b] += 1

    ans = [0] * n

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

    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]
# print(A)
# print(B)
for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1
# print(A)
# print(B)
 
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 size(self, x):
        return -self.parents[self.find(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 n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)
 
U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n
 
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]
# print(A)
# print(B)
for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1
# print(A)
# print(B)
 
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 size(self, x):
        # print(x)
        if self.parents[x] < 0:
            return -self.parents[x]  # 必ず正
        # if x<0:
        #     return -x
        # else:
        #     self.parents[x] = -abs(self.size(self.parents[x]))
        #     return abs(self.parents[x])
        else:
            self.parents[x] = -self.size(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 n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)
 
U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n
 
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [[] * n for _ in range(n)]

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

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

for i in range(k):
    c, d = [int(x) for x in input().split()]
    if same(c - 1, d - 1):
        cd[c - 1].append(d - 1)
        cd[d - 1].append(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

print(*ans)

Submission status: Accepted

Solution code:

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)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]
rank = [0 for _ in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    root_a = root(a, uni)
    root_b = root(b, uni)
    if root_a!=root_b:
        if rank[root_a] < rank[root_b]:
            uni[root_b] += uni[root_a]
            uni[root_a] = root_b
        else:
            uni[root_a] += uni[root_b]
            uni[root_b] = root_a
            if rank[root_a] == rank[root_b]:
                rank[root_a] += 1


for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)