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=map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(K)]

def root(x,P):
    l = []
    n = x
    p = P[n]
    while p >= 0:
        l.append(n)
        n = p
        p = P[p]
    for a in l: P[a] = n
    return n

def same(a, b, P): return root(a,P) == root(b,P)

def count(x,P): return -P[root(x,P)]

def unite(a, b, P):
    if count(a,P) < count(b,P): a, b = b, a
    ar = root(a,P)
    br = root(b,P)
    if ar == br: return
    P[ar] += P[br]
    P[br] = ar

Fu = [-1] * N
F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for a,b in AB:
    a, b = a-1, b-1
    unite(a,b,Fu)
    F[a].add(b)
    F[b].add(a)
for c,d in CD:
    c, d = c-1, d-1
    B[c].add(d)
    B[d].add(c)

for i in range(N):
    block = 0
    for b in B[i]:
        if same(i,b,Fu): block += 1
    print(count(i,Fu) - len(F[i]) - block - 1, end=' ')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, n):
        self.n = n + 1
        self.parents = [-1] * (n + 1)
        self.mem = [[] for _ in range(n+1)]

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

        if x == y:
            return

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        if not self.mem[root]:
            self.mem[root] = [i for i in range(1, self.n) if self.find(i) == root]
        return self.mem[root]

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

    friends = defaultdict(lambda : 1)
    friendsGroup = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friendsGroup.union(a, b)
        friends[a] += 1
        friends[b] += 1

    block_and_same = defaultdict(int)
    for _ in range(K):
        c, d = map(int, input().split())
        if friendsGroup.same(c, d):
            block_and_same[c] += 1
            block_and_same[d] += 1

    ans = [0] * (N + 1)
    for i in range(1, N+1):
        ans[i] = friendsGroup.size(i) - friends[i] - block_and_same[i]
    print(*ans[1:])

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

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

    u = UnionFind(n)

    ans = [0 for i in range(n)]

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

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

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

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

main()

Submission status: Accepted

Solution code:
class UnionFind:
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    
    uf.union(a, b)

    fr[a] = fr.get(a, 0) + 1
    fr[b] = fr.get(b, 0) + 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if not uf.is_same(c, d):
        continue

    fr[c] = fr.get(c, 0) + 1
    fr[d] = fr.get(d, 0) + 1


for i in range(N):
    s = uf.get_size(i) - 1
    s -= bl.get(i, 0)
    s -= fr.get(i, 0)
    print(s)

Submission status: Accepted

Solution code:
def solve():
    from collections import Counter
    import sys
    input = sys.stdin.readline

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

    # Union-Findデータ構造
    class UnionFind:
        def __init__(self, numV):
            self.pars = list(range(numV))
            self.ranks = [0] * numV
        def find(self, x):
            if self.pars[x] == x: return x
            else:
                self.pars[x] = self.find(self.pars[x])
                return self.pars[x]
        def union(self, x, y):
            x, y = self.find(x), self.find(y)
            if x == y: return
            if self.ranks[x] < self.ranks[y]:
                self.pars[x] = y
            else:
                self.pars[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1
        def same(self, x, y):
            return self.find(x) == self.find(y)

    UF = UnionFind(N)
    for A, B in ABs:
        A, B = A-1, B-1
        UF.union(A, B)

    for i in range(N):
        UF.find(i)

    cnt = Counter(UF.pars)
#    print('cnt:', cnt)

    anss = [cnt[UF.pars[i]]-1 for i in range(N)]
#    print('anss:', anss)

    for A, B in ABs:
        A, B = A-1, B-1
        if UF.same(A, B):
            anss[A] -= 1
            anss[B] -= 1
    for C, D in CDs:
        C, D = C-1, D-1
        if UF.same(C, D):
            anss[C] -= 1
            anss[D] -= 1

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


solve()

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

    u = UnionFind(n)

    ans = [0 for i in range(n)]

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

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

    for i in range(n):
        x = u.find(i)
        c = u.parents[x]
        ans[i] -= c + 1

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

main()

Submission status: Accepted

Solution code:
def inputs(): return (int(x) for x in 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())
N,M,K = inputs()
uf = UnionFind(N+1)
f = {i:[] for i in range(N)}
b = {i:[] for i in range(N)}
ans = [0]*(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    f[x-1].append(y-1)
    f[y-1].append(x-1)
    uf.union(x-1,y-1)
for _ in range(K):
    x,y = inputs()
    if uf.same(x-1,y-1):
        b[x-1].append(y-1)
        b[y-1].append(x-1)
for i in range(N):
    ans[i]+=uf.size(i)-len(f[i])-len(b[i])-1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M, K = map(int, input().split())
    uf_tree = UnionFind(N + 1)
    ans = [0] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        uf_tree.union(a, b)
        ans[a] -= 1
        ans[b] -= 1
    for _ in range(K):
        c, d = map(int, input().split())
        if uf_tree.same(c, d):
            ans[c] -= 1
            ans[d] -= 1
    
    for i in range(1, N + 1):
        ans[i] += uf_tree.size(i) - 1
    
    print(' '.join(map(str, ans[1:])))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict


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 resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(int)
    e = defaultdict(int)
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a] += 1
        d[b] += 1
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        if u.same(a, b):
            e[a] += 1
            e[b] += 1
    ans = [0] * n
    for i in range(n):
        ans[i] = u.size(i) - 1 - d[i] - e[i]
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
N,M,K=map(int,input().split())
s=[[]for i in range(N)]
tn=[0]*N
sys.setrecursionlimit(200000)
for i in range(M):
    a,b=map(int,input().split())
    s[a-1].append(b)
    s[b-1].append(a)
    tn[a-1]+=1
    tn[b-1]+=1
l=[None]*N
def hu(n,t):
    l[n]=t
    for i in s[n]:
        if l[i-1]==None:
            l[i-1]=t
            hu(i-1,t)
t=0
for i in range(N):
    if l[i]==None:
        hu(i,t)
        t+=1
c=[0]*t
for i in l:
    c[i]+=1
for i in range(K):
    a,b=map(int,input().split())
    if l[a-1]==l[b-1]:
        tn[a-1]+=1
        tn[b-1]+=1
for i in range(N):
    print(c[l[i]]-tn[i]-1,end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
# ブロック関係でないかつ同じグループ
class UnionFind():
    # nはノードの数
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    # xはノードの番号
    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、そのグラフの要素の個数を負の値で保持している
            return x
        else:
            # 再帰的に親を探しにいき、得られた値を格納する
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())  # N人の人, M人の友好関係, K個のブロック関係
uf = UnionFind(N)

# inはsetを使ってオーダー1
addjacent = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    addjacent[a].add(b)
    addjacent[b].add(a)
    uf.union(a, b)
blocked = defaultdict(list)
for _ in range(K):
    c, d = map(lambda x: int(x)-1, input().split())
    blocked[c].append(d)
    blocked[d].append(c)

# # 親の数だけ行う
# # print(pearents)
# ans = defaultdict(int)
# for group in pearents.values():
#     for n in group:
#         ans[n] = len(group) - 1 - len(addjacent[n]) - len(set(group)&blocked[n])
#     # groupの中にブロックがいるかどうか
#
# ans = " ".join(map(str, ans.values()))
# print(ans)

for i in range(N):
    cnt = 0
    for b in blocked[i]:
        if uf.same(i, b):
            cnt += 1
    print(uf.size(i) - len(addjacent[i]) - cnt - 1)

Submission status: Accepted

Solution code:
import sys

class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

input=sys.stdin.readline

N,M,K=map(int,input().split())
A=[0 for i in range(0,M)]
B=[0 for i in range(0,M)]
for i in range(0,M):
    A[i],B[i]=map(int,input().split())
C=[0 for i in range(0,K)]
D=[0 for i in range(0,K)]
for i in range(0,K):
    C[i],D[i]=map(int,input().split())

friend=[0 for i in range(0,N)]
for i in range(0,M):
    friend[A[i]-1]+=1
    friend[B[i]-1]+=1

uf=UnionFindVerSize(N)
for i in range(0,M):
    uf.unite(A[i]-1,B[i]-1)

block=[0 for i in range(0,N)]
for i in range(0,K):
    if uf.is_same_group(C[i]-1,D[i]-1):
        block[C[i]-1]+=1
        block[D[i]-1]+=1

ans=[0 for i in range(0,N)]
for i in range(0,N):
    ans[i]=uf.get_size(i)-friend[i]-block[i]-1
print(*ans)

Submission status: Accepted

Solution code:
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())
uf = UnionFind(N)
direct = [0] * N
for i in range(M):
	A,B = map(int,input().split())
	direct[A-1] += 1
	direct[B-1] += 1
	uf.union(A-1,B-1)
ans = [0] * N
for i in range(K):
	C,D = map(int,input().split())
	if uf.same(C-1,D-1) :
		direct[C-1] +=1
		direct[D-1] +=1
for i in range(N):
	ans[i] = uf.size(i) - direct[i] -1
print(*ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()

import collections
import itertools
import operator

class UnionFind:
  def __init__(self, elems=None):
    class KeyDict(dict):
      def __missing__(self, key):
        self[key] = key
        return key

    self.parent = KeyDict()
    self.rank = collections.defaultdict(int)
    self.size_ = collections.defaultdict(lambda: 1)

    if elems is not None:
      for elem in elems:
        _, _, _ = self.parent[elem], self.rank[elem], self.size_[elem]

  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.size_[y] += self.size_[x]
    else:
      self.parent[y] = x
      self.size_[x] += self.size_[y]
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

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

  def grouper(self):
    roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
    root = operator.itemgetter(1)
    for _, group in itertools.groupby(sorted(roots, key=root), root):
      yield [x for x, _ in group]

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

g = UnionFind()
fr = [0]*n

for i in range(m):
	a,b = na()
	g.unite(a,b)
	fr[a-1] -= 1
	fr[b-1] -= 1
for j in range(k):
	c,d = na()
	if g.are_same(c,d):
		fr[c-1] -= 1
		fr[d-1] -= 1

for p in range(n):
	fr[p] += (g.size(p+1)-1)

print(' '.join(str(s) for s in fr))

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans


'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''


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


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

gr = [i for i in range(n)]
es = []

for i in range(m):
    y,z = list(map(int, input().split()))
    es.append([min(y-1,z-1),max(y-1,z-1)])

es.sort(key=lambda x:x[0])
#print(es)

neigh = [[] for i in range(n)]
blocks = [[] for i in range(n)]

for i in range(m):
    neigh[es[i][0]].append(es[i][1])
    neigh[es[i][1]].append(es[i][0])

    
    
#print(neigh)


checked = [0 for i in range(n)]
nums = [1 for i in range(n)]

for i in range(n):
    if(checked[i]!=0):
        continue
    else:
        queue = [i]
        seen = [i]
        now=0
        checked[i]=1
        while(True):
            if(len(queue)==now):
                for j in range(len(seen)):
                    checked[seen[j]] = i
                    nums[seen[j]] = len(seen)
                break
            seeing = queue[now]
            
            now+=1
            for j in range(len(neigh[seeing])):
                if(checked[neigh[seeing][j]]==0):
                    queue.append(neigh[seeing][j])
                    checked[neigh[seeing][j]]=1
                    seen.append(neigh[seeing][j])


#print()
#print(checked)
#print(nums)

for i in range(k):
    y,z = list(map(int, input().split()))
    if(checked[y-1]==checked[z-1]):
        blocks[y-1].append(z-1)
        blocks[z-1].append(y-1)

ans = []
for i in range(n):
    ans.append( nums[i] - len(blocks[i]) - len(neigh[i]) - 1 )
print(' '.join(map(str,ans)))

Submission status: Accepted

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


class Tree:
    WHITE = -2
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u, c):
        if self.colors[u] >= 0:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.dfs(v, c)

        self.colors[u] = c

from collections import Counter

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

tree = Tree(adj)
for i in range(n):
    tree.dfs(i, i)

labels = tree.colors

counter = Counter(labels)

ans = [counter[labels[i]] - 1 for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    c -= 1
    d -= 1
    if labels[c] == labels[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:

class UnionFind(object):
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a] += 1
    else:
        fr[a] = 1

    if fr.get(b) is not None:
        fr[b] += 1
    else:
        fr[b] = 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if not uf.is_same(c, d):
        continue

    if bl.get(c) is not None:
        bl[c] += 1
    else:
        bl[c] = 1

    if bl.get(d) is not None:
        bl[d] += 1
    else:
        bl[d] = 1


for i in range(N):
    s = uf.get_size(i) - 1
    s -= bl.get(i, 0)
    s -= fr.get(i, 0)
    print(s)