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:
from itertools import chain

n,m,k = map(int,input().split())
 
bff = [list(map(int,input().split())) for i in range(m)]
 
blk = [list(map(int,input().split())) for i in range(k)]


rank = [0] * (n+1)
par = [i for i in range(n+1)]
demi = [1] * (n+1)


for i,j in bff:
    x = par[i]
    y = par[j]
    while x != par[x]:
        x = par[x]
    while y != par[y]:
        y = par[y]
    if(x == y):
        continue
    
    if rank[x] < rank[y]:
        par[x] = y
        demi[y] += demi[x]
        
    else:
        par[y] = x
        demi[x] += demi[y]
        
        if rank[x] == rank[y]:
             rank[x] += 1


for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    par[i+1] = x


for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    demi[i+1] = demi[x]



a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))

fqua = [0] * n
bqua = [0] * n
 
for i,j in bff:
    if(par[i] == par[j]):
        fqua[i-1] += 1
        fqua[j-1] += 1

for i,j in blk:
    if(par[i] == par[j]):
        bqua[i-1] += 1
        bqua[j-1] += 1

for i in range(n):
    print(demi[i+1] - fqua[i] - bqua[i] - 1 ,end=" ")

Submission status: Accepted

Solution code:
class union_find:
    def __init__(self, N):
        # par < 0 の時はsizeを格納
        self.par = [-1 for i in range(N)]
        self.excluded = [0 for i in range(N)]
    
    def root(self, a):
        if self.par[a] < 0:
            return a
        else:
            # 経路圧縮
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def unite(self, a, b):
        ar = self.root(a)
        br = self.root(b)
        if ar == br:
            return
        if self.par[ar] > self.par[br]:
            ar, br = br, ar
        self.par[ar] += self.par[br]
        self.par[br] = ar
    
    def friend(self, a, b):
        self.unite(a, b)
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def block(self, a, b):
        ar = self.root(a)
        br = self.root(b)
        if ar != br:
            return
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def get_friend_sugestion_size(self, a):
        return -self.par[self.root(a)] - 1 - self.excluded[a]

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def main():
    N, M, K = map(int, input().split())
    gf = [[] for _ in range(N)]
    gb = []
    for _ in range(M):
        a, b = [int(i) - 1 for i in input().split()]
        gf[a].append(b)
        gf[b].append(a)
    for _ in range(K):
        c, d = [int(i) - 1 for i in input().split()]
        gb.append((c, d))
    friend = defaultdict(int)
    ans = [0] * N
    par = [None] * N
    
    def dfs(v):
        if par[v] is None:  # 孤立している時は自分が親になる
            par[v] = v
            friend[par[v]] += 1
        for u in gf[v]:  # 隣接頂点の探索
            if par[u] is None:  # 孤立していたら親を一緒にする
                par[u] = par[v]
                friend[par[v]] += 1
                dfs(u)  # 再度探索する
    
    for i in range(N):
        if par[i] is None:
            dfs(i)
    for i in range(N):  # グラフサイズ - 隣接頂点数 - 自分自身
        ans[i] += friend[par[i]] - len(gf[i]) - 1
    for c, d in gb:
        if par[c] == par[d]:  # 「ブロック関係」で親が一緒の時は-1
            ans[c] -= 1
            ans[d] -= 1
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFindTree:
    """
    Union Find Tree

    Attributes
    ----------
    _parents : list
        Parents of each nodes.
        A parent of a root node is -1.
    _size : int
        The number of nodes of the tree
    _rank : int
        The size of a tree to which each root belongs to.
        If the node is not root, this rank might be incollect.
    """

    def __init__(self, size):
        """
        Parameters
        ----------
        size : int
            The number of nodes of the tree
        """
        self._size = size
        self._parents = [-1 for i in range(size)]
        self._rank = [1 for i in range(size)]

    def find(self, node):
        """
        Return the root of the node.
        If the node is root and have no parent, then return the node itself.

        Parameters
        ----------
        node : int
            A node whose parent will be returned.

        Returns
        -------
        root : int
            A parent of the node.
        """
        if self._parents[node] == -1:
            return node
        else:
            root = self.find(self._parents[node])
            self._parents[node] = root
            return root

    def union(self, node1, node2):
        """
        Unite two trees

        Parameters
        ----------
        node1 : int
            The first tree that will be united includes this node.
        node2 : int
            The first tree that will be united includes this node.
        """
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 == root2:
            # If node1 and node2 belong to the same tree, then do nothing.
            return
        rank1 = self._rank[root1]
        rank2 = self._rank[root2]
        if rank1 < rank2:
            self._parents[root1] = root2
            self._rank[root2] += rank1
        else:
            self._parents[root2] = root1
            self._rank[root1] += rank2

    def are_same(self, node1, node2):
        """
        Judges if two nodes belong to the same tree or not.

        Parameters
        ----------
        node1 : int
            The first node.
        node2 : int
            The second node.

        Returns
        : boolean
            If two nodes belong to the same tree or not.
        -------

        """
        if self.find(node1) == self.find(node2):
            return True
        else:
            return False

    def members_size(self, node):
        """
        Return the number of nodes that belong to the same tree include itself.

        Parameters
        ----------
        node

        Returns
        -------
        : int

        """
        return self._rank[self.find(node)]


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

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

potential_friends = [t.members_size(n) - 1 for n in range(N)]
for m in range(M):
    A, B = friends[m]
    if t.find(A - 1) == t.find(B - 1):
        potential_friends[A - 1] -= 1
        potential_friends[B - 1] -= 1

for k in range(K):
    C, D = map(int, input().split())
    if t.find(C - 1) == t.find(D - 1):
        potential_friends[C - 1] -= 1
        potential_friends[D - 1] -= 1

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

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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



def main():
    n,m,k = map(int,input().split())
    friend = [[] for i in range(n)]
    block = [[] for i in range(n)]

    for i in range(m):
        a,b = map(lambda x: int(x)-1,input().split())
        friend[a].append(b)
        friend[b].append(a)
    # print(friend)
    
    for i in range(k):
        c,d = map(lambda x:int(x)-1,input().split())
        block[c].append(d)
        block[d].append(c)
    
    # print(block)

    un = UnionFind(n)
    
    for i in range(len(friend)):
        for j in range(len(friend[i])):
            # print(i,friend[i][j])
            un.union(i,friend[i][j])
    
    ans = []
    for i in range(len(block)):
        cnt = 0
        for j in range(len(block[i])):
            # print(i,block[i][j])
            if un.find(i) == un.find(block[i][j]):
                cnt += 1
        ans.append(str(un.size(i)-len(friend[i]) - cnt - 1))

    # for i in range(n):
    #     # ans.append(str(len((set(un.members(i)) - (set(block[i])|set(friend[i]))))-1))
    #     print(un.size(i))
    #     print(len(friend[i]))
    #     print(len(block[i]))
    #     ans.append(str( un.size(i) - len(friend[i]) - len(block[i]) -1))

    print(' '.join(ans))

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
INF = float("inf")


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 各要素の親要素の番号を格納するリスト

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素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())


def main():
    N, M, K = map(int, input().split())
    graph_friends =[[] for _ in range(N)]
    uf_friends = UnionFind(N)
    for _ in range(M):
        a, b = [int(i) - 1 for i in input().split()]
        graph_friends[a].append(b)
        graph_friends[b].append(a)
        uf_friends.union(a, b)

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

    ans = [0] * N
    for i in range(N):
        size = uf_friends.size(i) - 1
        for f in graph_friends[i]:  # 「友達関係」の時は外す
            if uf_friends.same(i, f):  # 隣接して絵いるかつ親が同じ
                size -= 1
        for b in graph_block[i]:  # 「ブラック関係」の時は外す
            if uf_friends.same(i, b):  # 隣接してるかつ親が同じ
                size -= 1
        ans[i] = size
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

# ここにいたるまで結構かかる
# https://note.nkmk.me/python-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
        
        # 根のparentsはそのグループの要素数 * (-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)]

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

dame = [set() for _ in range(N)]
uf = UnionFind(N)

for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    uf.union(a, b)
    dame[a].add(b)
    dame[b].add(a)

for _ in range(K):
    c, d = list(map(int, input().split()))
    c -= 1
    d -= 1
    if uf.find(c) == uf.find(d):
        dame[c].add(d)
        dame[d].add(c)

ans = []
for i in range(N):
    ans.append(uf.size(i) - len(dame[i]) -1 )

for val in ans:
    print(val, end=" ")
print("\n")

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
print(*ans[1:])

Submission status: Accepted

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

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

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

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque, Counter
N, M, K = list(map(int, input().split()))
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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

# まだ探索済みでない頂点からdfs
# どの頂点がどの連結成分に属するかを管理
connect_group = {}

for i in range(N):
    if connect_group.get(i) is not None:
        continue
    stack = deque()
    stack.append(i)
    connect_group[i] = i
    p = -1    
    while len(stack):
        j = stack.pop()
        connect_group[j] = i
        for k in F[j]:
            if connect_group.get(k) is None:
                stack.append(k)
                connect_group[k] = i


ans = []
connect_len = Counter(connect_group.values())
for i in range(N):
    g = connect_group[i]
    l = connect_len[g]
    x = 0
    for j in set(F[i]).union(set(B[i])):
        if g == connect_group[j]:
            x += 1
    ans.append(str(l - x - 1))

print(' '.join(ans))

Submission status: Accepted

Solution code:
class UnionFindTree:
    
    def __init__(self, n):
        if n == 0:
            raise Exception("n is more than 1")
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.num = {}
        for i in range(n):
            self.num.update({i:1})
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.num[y] += self.num[x]
            del self.num[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.num[x] += self.num[y]
            del self.num[y]
        
    
    def same(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        return X == Y

def add_dict(d, a, b):
    d[a].append(b)
    d[b].append(a)

def Main(N, M, K, A, B, C, D):
    uft = UnionFindTree(N)
    df = {}
    db = {}
    for i in range(N):
        df.update({i:[]})
        db.update({i:[]})
    for i in range(M):
        uft.unite(A[i]-1, B[i]-1)
        add_dict(df, A[i]-1, B[i]-1)
    for i in range(K):
        add_dict(db, C[i]-1, D[i]-1)
    ans = []
    for i in range(N):
        num_b = 0
        for e in db[i]:
            if uft.same(i, e):
                num_b += 1
        a = uft.num[uft.find(i)] - len(df[i]) - num_b - 1
        ans.append(str(a))
    return ans
                    
def main():
    N, M, K = map(int, input().split())
    A = []
    B = []
    C = []
    D = []
    for i in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    for i in range(K):
        c, d = map(int, input().split())
        C.append(c)
        D.append(d)
    out = Main(N, M, K, A, B, C, D)
    print(" ".join(out))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
# ]
#
# BRR = [
#     [2, 6],
#     [7, 5],
#     [3, 1],
# ]
#
# fl = [[] for i in range(N)]
# bl = [[] for i in range(N)]

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

ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

BRR = []
for i in range(K):
    BRR.append(list(map(int,input().split())))

unionFind = UnionFind(N)

fl = [[] for i in range(N)]
bl = [[] for i in range(N)]
for ar in ARR:
    fromNode = ar[0] - 1
    toNode = ar[1] - 1
    unionFind.union(fromNode, toNode)
    fl[fromNode].append(toNode)
    fl[toNode].append(fromNode)

for br in BRR:
    fromNode = br[0] - 1
    toNode = br[1] - 1
    bl[fromNode].append(toNode)
    bl[toNode].append(fromNode)

result = []
for i in range(N):
    size = unionFind.size(i) - 1


    for f in fl[i]:
        if unionFind.same(i,f):
            size = size - 1
    for b in bl[i]:
        if unionFind.same(i,b):
            size = size - 1

    result.append(str(size))

print(" ".join(result))

Submission status: Accepted

Solution code:
from collections import deque,Counter
n,m,k = map(int,input().split())
G = [[] for _ in range(n)]

exc = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    exc[a] += 1
    exc[b] += 1

stk = deque()
grp = [-1]*n
grpnum = 0
def dfs(s,g):
    stk.append(s)
    grp[s] = g
    while stk:
        cur = stk.pop()
        for nxt in G[cur]:
            if grp[nxt] != -1: continue
            grp[nxt] = g
            stk.append(nxt)

for i in range(n):
    if grp[i] != -1: continue
    dfs(i,grpnum)
    grpnum += 1
cnt = Counter(grp)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if grp[c] == grp[d]:
        exc[c] += 1
        exc[d] += 1

ans = [cnt[grp[i]] - exc[i] - 1 for i in range(n)]
print(*ans)

Submission status: Accepted

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

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

#先ずは連結成分の数を調べる
G = defaultdict(lambda:deque([]))
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

NIL = -1
color = [NIL]*n
def dfs(r, c):
    S = deque([])
    S.append(r)
    color[r] = c
    while S:
        u = S.popleft()
        for v in G[u]:
            if color[v] == NIL:
                color[v] = c
                S.append(v)
                
def make_color():
    id = 1
    for u in range(n):
        if color[u] == NIL:
            dfs(u, id)
            id += 1
            
make_color()
#グラフの塗り分け完了

#各色ごとの連結成分の数を数える
count = defaultdict(lambda:0)
for i in range(n):
    count[i] = 0
for i in range(n):
    count[color[i]] += 1

#ブロック関係の辞書を作成
block = defaultdict(lambda:deque([]))
for _ in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    block[c].append(d)
    block[d].append(c)

temp = []
for i in range(n):
    x = count[color[i]] - 1#自分以外の連結成分の和
    y =  len(G[i])#友達の数
    z = 0 #連結内のブロック数
    for v in block[i]:
        if color[i] == color[v]:
            z += 1
    temp.append(x-y-z)
print(*temp)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

    def root(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

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

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

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

n,m,k = map(int,input().split())
cnt = [0]*n
ds = DisjointSet(n)
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    cnt[a] += 1
    cnt[b] += 1
    ds.unite(a,b)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if ds.same(c,d):
        cnt[c] += 1
        cnt[d] += 1
ans = [ds.size(i) - cnt[i] - 1 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 find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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

        if x == y:
            return

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

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

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

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

def solve(uf, except_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(uf.size(i) - 1 - len(except_list[i]))
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    except_list = [[] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        except_list[a].append(b)
        except_list[b].append(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        if not uf.same(c, d):
            continue
        except_list[c].append(d)
        except_list[d].append(c)

    for ans in solve(uf, except_list)[1:]:
        print(ans, end=' ')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())


    class UnionFind:
        def __init__(self, n):
            self.table = [i for i in range(n)]
            self.rank = [0] * n
            self.group_size = [1] * n
        
        def find_root(self, i):
            if self.table[i] == i:
                return i
            root = self.find_root(self.table[i])
            self.table[i] = root    # 経路圧縮
            return root
        
        def is_same(self, x, y):
            return self.find_root(x) == self.find_root(y)
        
        def union(self, x, y):
            s = self.find_root(x)
            t = self.find_root(y)
            if s == t:
                return False
            else:
                if self.rank[s] > self.rank[t]:
                    s, t = t, s
                self.table[s] = t
                self.group_size[t] += self.group_size[s]
                if self.rank[s] == self.rank[t]:
                    self.rank[t] += 1
                return True
        
        def num_of_members(self, i):
            root = self.find_root(i)
            return self.group_size[root]
    

    n, m, k = lmi()
    adj_friend = [[] for _ in range(n)]
    for _ in range(m):
        a, b = mi_0()
        adj_friend[a].append(b)
        adj_friend[b].append(a)
    adj_rival = [[] for _ in range(n)]
    for _ in range(k):
        c, d = mi_0()
        adj_rival[c].append(d)
        adj_rival[d].append(c)
    
    uf = UnionFind(n)
    for i, elm in enumerate(adj_friend):
        for j in elm:
            if i < j:
                uf.union(i, j)
    
    for i in range(n):
        connected = uf.num_of_members(i)
        connected_rival = 0
        for rival in adj_rival[i]:
            if uf.is_same(i, rival):
                connected_rival += 1
        # print(f"{connected} {connected_rival} {len(adj_friend[i])}")
        print(connected - connected_rival - len(adj_friend[i]) - 1, end=' ')    # 自分を引くことを忘れずに
    print('')
    

if __name__ == "__main__":
    main()