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:
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

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

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)

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
    fre = [set() for _ in range(N)]
    blo = [set() for _ in range(N)]
    mem = {i for i in range(N)}
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        fre[a-1].add(b-1)
        fre[b-1].add(a-1)
        unite(a-1, b-1)
    cur = [-1]*N
    from collections import Counter
    for i, x in enumerate(par):
        unite(i, x)
    c = Counter(par)
    # print(par, is_same_group(5, 7))
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            blo[a-1].add(b-1)
            blo[b-1].add(a-1)
    for i in range(N):
        cur = c[par[i]] - len(fre[i]) - len(blo[i]) - 1
        print(cur, end=" ")
    print()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import collections

N,M,K=map(int,input().split())
F=[[] for i in range(N+1)]
Bl=[[] for i in range(N+1)]

par = [i for i in range(N+1)]
rank = [0 for i in range(N+1)]
 
def find(x):
    if x==par[x]:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
 
def unite(x,y):
    rx=find(x)
    ry=find(y)

    if rx==ry:
        return
    
    
    if rank[rx]<rank[ry]:
        par[rx]=ry
    else:
        par[ry]=rx

    if rank[rx]==rank[ry]:
        rank[rx]+=1
 

def some(x,y):
    return find(x)==find(y)
 
for i in range(M):
    A,B=map(int,input().split())
    unite(A,B)
    F[A].append(B)
    F[B].append(A)

for i in range(K):
    C,D=map(int,input().split())
    Bl[C].append(D)
    Bl[D].append(C)

ans=[0 for i in range(N)]
for i in range(N):
    find(i+1)
c = collections.Counter(par)

for i in range(N):
    ans[i]+=c[find(i+1)]-1
    ans[i]-=len(F[i+1])
    for j in range(len(Bl[i+1])):
        if some(i+1,Bl[i+1][j]):
            ans[i]-=1
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,m,k = map(int, input().split())
vw = []
graph = {}
for i in range(m):
    v,w = map(int,input().split())
    v -= 1
    w -= 1
    vw.append((v,w))
    if v not in graph:
        graph[v] = {}
    if w not in graph:
        graph[w] = {}
    graph[v][w] = graph[w][v] = 1

block = {}
for i in range(k):
    v,w = map(int , input().split())
    v -= 1
    w -= 1
    if v not in block:
        block[v] = {}
    if w not in block:
        block[w] = {}
    block[v][w] = block[w][v] = 1

cnt = [1 for _ in range(n+1)]
par = [i for i in range(n+1)]

for a,b in vw:
    aa = get_par(par, a)
    bb = get_par(par, b)
    if aa == bb:
        continue
    # unite
    if cnt[aa] > cnt[bb]:
        par[bb] = aa
        cnt[aa] += cnt[bb]
    else:
        par[aa] = bb
        cnt[bb] += cnt[aa]

bbb = []
for i in range(n):
    a = get_par(par, i)
    ans = cnt[a] - len(graph.get(i,[])) - 1
    # print(i, ans, cnt[a], graph.get(i,[]))
    if i not in block:
        bbb.append(ans)
        continue
    # print(block[i])
    for v in block[i].keys():
        if get_par(par, v) == a:
            ans -= 1
    bbb.append(ans)
print(*bbb)

Submission status: Accepted

Solution code:
class UnionFindBySize():
    def __init__(self, n):
        self.parents = list(range(n+1))
        self.size = [1] * (n+1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # 根が同一かどうかを判定する
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

n, m, k = map(int, input().split())
AB_dict = {x:[] for x in range(1, n+1)}
AB = []
CD_dict = {x:[] for x in range(1, n+1)}
CD = []
for _ in range(m):
    a, b = map(int, input().split())
    AB_dict[a].append(b)
    AB_dict[b].append(a)
    AB.append([a,b])
for _ in range(k):
    c, d = map(int, input().split())
    CD_dict[c].append(d)
    CD_dict[d].append(c)
    CD.append([c,d])

UF = UnionFindBySize(n)
for i in range(m):
    UF.union(AB[i][0], AB[i][1])

# print(UF.size)
Ans = []
for i in range(n):
    same_tree_block = 0
    size = UF.size[UF.find(i+1)]
    for x in CD_dict[i+1]:
        same_tree_block += UF.same_check(i+1, x)
    friends = len(AB_dict[i+1])
    # print('-'*30)
    # print('i+1 is ' + str(i+1))
    # print('cand is ' + str(size))
    # print('same_tree_block is ' + str(same_tree_block))
    # print('friends is ' + str(friends))
    ans = size - same_tree_block - friends -1
    Ans.append(str(ans))
print(' '.join(Ans))

Submission status: Accepted

Solution code:
import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [[] for _ in range(n+1)]
for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)
block = [[] for _ in range(n+1)]
for c, d in cd:
    block[c].append(d)
    block[d].append(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)

    for u in range(1, n+1):
        find_root(u)

    for u in range(1, n+1):
        ru = root[u]
        cnt = size[ru] - 1  - len(friend[u])
        for v in block[u]:
            if root[v] == ru:
                cnt -= 1
        yield cnt

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

Submission status: Accepted

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

# #friend = [[0 for _ in range(n)] for _ in range(n)]
friend = [1 for _ in range(n)]
uf = UnionFind(n)

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

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

# print(uf)
for i in range(n):
    if i != n-1:
        print(uf.size(i) - friend[i], end=" ")
    else:
        print(uf.size(i) - friend[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    par = list(range(N))
    rank = [0] * N

    def find(x):
        if par[x] == x:
            return x
        par[x] = find(par[x])
        return par[x]

    def unite(x, y):
        x = find(x)
        y = find(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

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

    friend = collections.defaultdict(set)
    for i in range(M):
        a = A[i] - 1
        b = B[i] - 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)

    block = collections.defaultdict(set)
    for i in range(K):
        c = C[i] - 1
        d = D[i] - 1
        block[c].add(d)
        block[d].add(c)

    tomodatinowa = [0] * N
    for i in range(N):
        tomodatinowa[find(i)] += 1

    res = [0] * N
    for i in range(N):
        res[i] = tomodatinowa[par[i]] - 1
        for bl in block[i]:
            if same(i, bl):
                res[i] -= 1
        for fr in friend[i]:
            if same(i, fr):
                res[i] -= 1

    print(" ".join(str(a) for a in res))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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]
            return self.find(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)
#初期化したら友達関係を受け取ってufを形成していく union
friend = [0]*n
# 友達が何人いるかも必要
for i in range(m):
    a,b = map(int,input().split())
    friend[a-1] += 1
    friend[b-1] += 1
    uf.union(a-1,b-1)
# uf が完成したら,c,d を受け取り、parentの値が同じならblock[c],bloc[d]+=1をする
block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    #print(abs(uf.parents[uf.find(i)]),":",i)
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

Submission status: Accepted

Solution code:
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.size_ = [1 for _  in range(size)] 
    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x
    #併合
    def find_size(self,x):
        s1=self.find(x)
        return self.size_[s1]
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
            a=self.size_[s1]+self.size_[s2]
            self.size_[s1]=a
            self.size_[s2]=a
        return
N,M,K=map(int,input().split())
count=[-1 for i in range(N)]
G = UnionFind(N)
for i in range(M):
    A,B=map(int,input().split())
    if A != B:#自己ループは実装しない
        G.union(A-1,B-1)
        count[A-1]-=1
        count[B-1]-=1
for i in range(N):
    count[i]+=G.find_size(i)
for j in range(K):
    C,D=map(int,input().split())
    if G.find(C-1) == G.find(D-1):
        count[C-1]-=1
        count[D-1]-=1
print(*count)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M, K = map(int, input().split())
uf_fr = UnionFind(N)
n_friends = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    n_friends[a] += 1
    n_friends[b] += 1
    uf_fr.union(a, b)
ans = [uf_fr.size(i) - 1 - n_friends[i] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if uf_fr.is_connected(a, b):
        ans[a] -= 1; ans[b] -= 1
print(*ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

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, sys.stdin.readline().strip().split())
friends_set = [set() for _ in range(N)]
block_set = [set() for _ in range(N)]

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    uf.union(a-1, b-1)
    friends_set[a-1].add(b-1)
    friends_set[b-1].add(a-1)

for _ in range(K):
    c, d = map(int, sys.stdin.readline().strip().split())
    block_set[c-1].add(d-1)
    block_set[d-1].add(c-1)

# print(uf)
for i in range(N):
    # n = uf.find(i)
    # print(len(uf.members(n)), len(friends_set[i]), len(block_set[i]))
    # print(uf.members(n), friends_set[i], block_set[i])

    # TLE
    # print(len(set(uf.members(n)) - set([i]) - friends_set[i] - block_set[i]), end = " ")

    blocked = 0
    for j in block_set[i]:
        if uf.same(i, j):
            blocked += 1
    print(uf.size(i) - 1 - len(friends_set[i]) - blocked, end = " ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
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):
    #     if self.parents[x] < 0:
    #         return -self.parents[x]
    #     else:
    #         self.parents[x] = self.size(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])
    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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1

n, m, k = LI()
G = [set() for _ in range(n)]
G2 = [set() for _ in range(n)]
U = UnionFind(n)
for _ in range(m):
    a, b = LI()
    U.union(a - 1, b - 1)
    G2[a - 1].add(b - 1)
    G2[b - 1].add(a - 1)

for _ in range(k):
    a, b = LI()
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)


D = defaultdict(lambda:set())
for i in range(n):
    D[U.root(i)].add(i)

for i in range(n):
    i_set = D[U.root(i)]
    ret = len(i_set) - 1
    for j in G2[i]:
        if j in i_set:
            ret -= 1
    for k in G[i]:
        if k in i_set:
            ret -= 1
    print(ret, end='\t')

Submission status: Accepted

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

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 set(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+1)
for a,b in ab:
    uf.union(a,b)

f_num = [1] * (n+1)
b_num = [0] * (n+1)

for a,b in ab:
    f_num[a] += 1
    f_num[b] += 1

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

ans = [0] * (n+1)

for i in range(1,n+1):
    ans[i] = uf.size(i) - f_num[i] - b_num[i]

print(' '.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
# from bisect import *
from collections import *
# from heapq import *
# INF = 500000
mod = 10**9+7

class UnionFind:

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

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M, K = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    es[u].append(v)
    es[v].append(u)
uf = UnionFind(N)
g = [-1]*N
def dfs(v, num):
    g[v] = num
    for u in es[v]:
        if g[u] == -1:
            uf.unite(v, u)
            dfs(u, num)
num = 0
for v in range(N):
    if g[v] == -1:
        dfs(v, num)
        num += 1
ans = [uf.getsize(v)-len(es[v])-1 for v in range(N)]
for i in range(K):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if uf.same(u, v):
        ans[u] -= 1
        ans[v] -= 1
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter


class UnionFind(object):
    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 main():
    n, m, k = list(map(int, sys.stdin.readline().strip().split()))

    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = list(map(int, sys.stdin.readline().strip().split()))
        a -= 1
        b -= 1
        friends[a].add(b)
        friends[b].add(a)

    for i in range(k):
        c, d = list(map(int, sys.stdin.readline().strip().split()))
        c -= 1
        d -= 1
        blocks[c].add(d)
        blocks[d].add(c)

    uf = UnionFind(n)

    for f_key in friends:
        for child in friends[f_key]:
            # child_cur_group = parents[child]
            uf.union(f_key, child)

    # group_num_set = defaultdict(set)
    # for i in range(n):
    #     group = uf.find(i)
    #     group_num_set[group].add(i)

    ans = [0] * n
    for i in range(n):
        group = uf.find(i)
        size = uf.size(i) - 1
        size -= len(friends[i])
        for block in blocks[i]:
            block_group = uf.find(block)
            if block_group == group:
                size -= 1
        ans[i] = size


        # friend_cand = group_num_set[group]

        # true_friend_cand = friend_cand.difference(blocks[i]).difference(friends[i])
        # ans[i] = len(true_friend_cand) - 1

    return ans


result = main()
print(' '.join([str(num) for num in result]))