Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

def main():
    N,M,K=mis()
    uf = UnionFindEx(N)
    frs = tuple(set() for _ in range(N))
    bls = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = mis()
        uf.connect(a-1, b-1)
        frs[a-1].add(b-1)
        frs[b-1].add(a-1)
    for _ in range(K):
        a, b = mis()
        bls[a-1].add(b-1)
        bls[b-1].add(a-1)
    for i in range(N):
        print(uf.getGroupSize(i) - len(frs[i]) - sum(uf.getRootID(i)==uf.getRootID(k) for k in bls[i]) - 1, end=' ')


main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
G = [[] for _ in range(N)]
deg = [0 for _ in range(N)]
reds = [[] for _ in range(N)]

for _ in range(M):
    _a, _b = list(map(int, input().split()))
    _a -= 1
    _b -= 1
    G[_a].append(_b)
    G[_b].append(_a)
    deg[_a] += 1
    deg[_b] += 1


# compute connected components
numbers = {i: None for i in range(N)}

def dfs():
    visited = [False for _ in range(N)]
    stack = []
    for i in range(N):
        if not visited[i]:
            stack.append(i)
            while len(stack) > 0:
                v = stack.pop()
                visited[v] = True
                numbers[v] = i
                for neighbor in G[v]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
dfs()

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    _c -= 1
    _d -= 1
    if numbers[_c] == numbers[_d]:
        reds[_c].append(_d)
        reds[_d].append(_c)

counter = {}
for i in range(N):
    if numbers[i] not in counter:
        counter[numbers[i]] = 1
    else:
        counter[numbers[i]] += 1

for i in range(N):
    v = counter[numbers[i]] - len(G[i]) - len(reds[i]) - 1
    print(v, end='')
    if i < N - 1:
        print(" ", end='')
print()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

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

    fre = [[] for i in range(n)]

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

    group = [-1]*n
    def check():
        dic = {}
        count = 1
        for i in range(n):
            if group[i] == -1:
                a = dfs(i,count)
                dic[count] = a
                count += 1
        return group,dic

    def dfs(i,count):
        num = 0
        group[i] = count
        q = deque([])
        q.append(i)
        while q:
            bef = q.pop()

            for nex in fre[bef]:
                if group[nex] == -1:
                    group[nex] = count
                    q.append(nex)
                    num += 1
        return num
    group,dic = check()
    ans = []
    for i in range(n):
        a = group[i]
        ans.append([dic[a]-len(fre[i]),a])
    for i in range(k):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        if ans[a][1] == ans[b][1]:
            ans[a][0] -= 1
            ans[b][0] -= 1
    for i,j in ans:
        print(i,end=" ")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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


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

    # 検索
    def find(self, 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 = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.union(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block):
            ans[iam] -= 1

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
from collections import deque
n, m, k =map(int, input().split())

directcount = [0] * n # node_iが直接接続しているノードの数
visited = [-1]  * n # nodeの色,
colorcount = [-1] * n # 各色が何個のノードを持つか
# グラフの初期化
g = []
for _ in range(n):
    g.append(deque(list()))

# グラフの生成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1 # 1origin -> 0 origin
    g[a].append(b)
    g[b].append(a)
    # 直接接続されているノードの数
    directcount[a] += 1
    directcount[b] += 1

# dfs 連結したグラフごとにそのグラフの最初に探索したnodeの色に染める
q = deque(list()) #探索キュー
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        nextnode = q.popleft() # 次の探索
        if visited[nextnode] != -1:
            continue
        visited[nextnode] = color
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1
    # 探索が終わったらその色のノードの数を記録
    colorcount[color]  = cnt - 1

# res[i] = ノードの色, その色のノードの数 - そのノードが直接接続しているノード数 - 自分自身(1)　で初期化する
res = [[visited[i], colorcount[visited[i]] - (directcount[i] + 1)] for i in range(n)]

# ブロックリスト
for i in range(k):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1 # 1 origin -> 0 origin
    # ブロック関係が同じ色だとするなら
    if res[c][0] == res[d][0]:
        # 友達になれると思っていた数を1つ減らす
        res[c][1] -= 1
        res[d][1] -= 1

# 各ノードから「直接つながっているノード」と「自分自身=1」を抜く
#for i in range(n):
#    res[i][1] -= (directcount[i] + 1)

# 結果の表示
print(" ".join(list(map(lambda x: str(x[1]), res))))

Submission status: Accepted

Solution code:
def main():
    n,m,k = map(int,input().split())
    friend = []
    block = []
    # Union-Find作る
    uf = UnionFind(n)
    #　iとすでに友達　iとブロックの数は最後に除外する
    exclude_i = [0] * n

    for _ in range(m):
        a,bb = map(int,input().split())
        # aとbを同じグループにする
        uf.union(a-1,bb-1)
        friend.append([a-1,bb-1])

    for _ in range(k):
        c,d = map(int,input().split())
        block.append([c-1,d-1])
        # CとDが友達候補（同じグループ）なら除外する　可哀想
        if uf.same(c-1,d-1):
            exclude_i[c-1] += 1
            exclude_i[d-1] += 1


    for i, f in enumerate(friend):
        # すでに友達ならそれは友達候補ではなく、もはや親友なんだよ（除外）
        if uf.same(f[0],f[1]):
            exclude_i[f[0]] += 1
            exclude_i[f[1]] += 1



    for i in range(n):
        # uf.sizeは自分を含んでるから、自分を除外する-1
        print(str(uf.size(i)-exclude_i[i]-1 ), end = " ")
    print("")

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


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m, k =map(int, input().split())

directcount = [0] * n # node_iが直接接続しているノードの数
visited = [-1]  * n # nodeの色,
colorcount = [-1] * n # 各色が何個のノードを持つか
# グラフの初期化
g = []
for _ in range(n):
    g.append(deque(list()))

# グラフの生成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1 # 1origin -> 0 origin
    g[a].append(b)
    g[b].append(a)
    # 直接接続されているノードの数
    directcount[a] += 1
    directcount[b] += 1

# dfs 連結したグラフごとにそのグラフの最初に探索したnodeの色に染める
q = deque(list()) #探索キュー
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        nextnode = q.popleft() # 次の探索
        if visited[nextnode] != -1:
            continue
        visited[nextnode] = color
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1
    # 探索が終わったらその色のノードの数を記録
    colorcount[color]  = cnt - 1

# res[i] = ノードの色, その色のノードの数　で初期化する
res = [[visited[i], colorcount[visited[i]] - (directcount[i] + 1)] for i in range(n)]

# ブロックリスト
for i in range(k):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1 # 1 origin -> 0 origin
    # ブロック関係が同じ色だとするなら
    if res[c][0] == res[d][0]:
        # 友達になれると思っていた数を1つ減らす
        res[c][1] -= 1
        res[d][1] -= 1

# 各ノードから「直接つながっているノード」と「自分自身=1」を抜く
#for i in range(n):
#    res[i][1] -= (directcount[i] + 1)

# 結果の表示
print(" ".join(list(map(lambda x: str(x[1]), res))))

Submission status: Accepted

Solution code:
def main():
    n,m,k = map(int,input().split())
    # frend = [[10**6] * n for i in range(n)]
    # block = [[0] * n for i in range(n)]
    # f = [[0]*n for i in range(n)]
    fq = []
    # b = [[0]*n for i in range(n)]
    bq = []
    uf = UnionFind(n)
    dame = [0] * n

    for _ in range(m):
        a,bb = map(int,input().split())
        # f[a-1][bb-1] = 1
        # f[bb-1][a-1] = 1
        uf.union(a-1,bb-1)
        fq.append([a-1,bb-1])

    for _ in range(k):
        c,d = map(int,input().split())
        # b[c-1][d-1] = 1
        # b[d-1][c-1] = 1
        bq.append([c-1,d-1])
        if uf.same(c-1,d-1):
            dame[c-1] += 1
            dame[d-1] += 1


    for i, ff in enumerate(fq):
        if uf.same(ff[0],ff[1]):
            dame[ff[0]] += 1
            dame[ff[1]] += 1



    for i in range(n):
        print(str(uf.size(i)-dame[i]-1 ), end = " ")
    print("")

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


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m, k =map(int, input().split())

fd = dict()
directcount = [0] * n
visited = [[-1, -1] for i in range(n)]
q = deque(list())
g = []
for _ in range(n):
    g.append(deque(list()))

for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1 # 1origin -> 0 origin
    g[a].append(b)
    g[b].append(a)
    directcount[a] += 1
    directcount[b] += 1

colorcount = [-1] * n
# dfs
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        #print(q)
        nextnode = q.popleft() # 次の探索
        if visited[nextnode][0] != -1:
            continue
        visited[nextnode] = [color, cnt]
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1
    colorcount[color]  = cnt - 1

res = [[visited[i][0], colorcount[visited[i][0]]] for i in range(n)]

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

for i in range(n):
    res[i][1] -=  (directcount[i] + 1)
print(" ".join(list(map(lambda x: str(x[1]), res))))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import Counter


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return 
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
    
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


N, M, K = list(map(int, input().split()))
edges1 = [[] for _ in range(N + 1)]
edges2 = [[] for _ in range(N + 1)]
uf = UnionFind(N)

A, B = [], []
C, D = [], []
for _ in range(M):
    _a, _b = list(map(int, input().split()))
    A.append(_a)
    B.append(_b)
    uf.unite(_a, _b)
    edges1[_a].append(_b)
    edges1[_b].append(_a)

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    C.append(_c)
    D.append(_d)
    edges2[_c].append(_d)
    edges2[_d].append(_c)

i, blocked = 1, 0
for b in edges2[1]:
    if uf.is_same_group(i, b):
        blocked += 1
print(uf.count(i) - 1 - len(edges1[i]) - blocked, end='')

for i in range(2, N + 1):
    print(' ', end='')
    blocked = 0
    for b in edges2[i]:
        if uf.is_same_group(i, b):
            blocked += 1
    print(uf.count(i) - 1 - len(edges1[i]) - blocked, end='')
print()

Submission status: Accepted

Solution code:
from collections import deque
n, m, k =map(int, input().split())


fd = dict()
directcount = [0] * n
visited = [[-1, -1] for i in range(n)]
q = deque(list())
g = []
for _ in range(n):
    g.append(deque(list()))


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    directcount[a] += 1
    directcount[b] += 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True

colorcount = [-1] * n
# dfs
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        #print(q)
        nextnode = q.popleft() # 次の探索
        if visited[nextnode][0] != -1:
            continue
        visited[nextnode] = [color, cnt]
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1
    colorcount[color]  = cnt - 1

# グループごとの色をカウント
#for i in range(n):
#    colorcount[visited[i][0]] = max(colorcount[visited[i][0]], visited[i][1])

#print(visited)
#print(colorcount)


res = [[visited[i][0], colorcount[visited[i][0]]] for i in range(n)]
#print(res)

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

output = []
for i in range(n):
    output.append(res[i][1] - directcount[i] - 1)

print(" ".join(list(map(lambda x: str(x), output))))

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)
 
    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
 
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
 
    def members(self, x):
        root = self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.root) 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 size(self, x):
        return -self.root[self.Find_Root(x)]
 
 
n, m, k = map(int, input().split())
 
uf = UnionFind(n)
directcount = [0] * n
 
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    directcount[a] += 1
    directcount[b] += 1
    uf.Unite(a, b)
 
res = []
for _ in range(n):
    res.append( [0, -1] )
ures = []
 
for i in range(n):
    res[i][0] = uf.size(i) - directcount[i] -1
    res[i][1] = uf.Find_Root(i)
#print(res)
 
 
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if res[c][1] == res[d][1]:
        res[c][0] -= 1
        res[d][0] -= 1
 
 
print(" ".join(list(map(lambda x: str(x[0]), res))))

Submission status: Accepted

Solution code:
from collections import deque


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

g = []
# Init Graph
for _ in range(n):
    g.append(deque(list()))


bd = dict()
fd = dict()

directcount = [0] * n


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    directcount[a] += 1
    directcount[b] += 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True

visited = [[-1, -1] for i in range(n)]
q = deque(list())
# dfs
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        #print(q)
        nextnode = q.popleft() # 次の探索
        #print("next", nextnode)
        if visited[nextnode][0] != -1:
            #print("visited")
            continue
        visited[nextnode] = [color, cnt]
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1

colorcount = [-1] * n
# グループごとの色をカウント
for i in range(n):
    colorcount[visited[i][0]] = max(colorcount[visited[i][0]], visited[i][1])

#print(visited)
#print(colorcount)


res = [[visited[i][0], colorcount[visited[i][0]]] for i in range(n)]
#print(res)

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

output = []
for i in range(n):
    output.append(res[i][1] - directcount[i] - 1)

print(" ".join(list(map(lambda x: str(x), output))))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parent=list(range(n))
    self.size=[1]*n
    #print(self.size, end=" self.size \n")
  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 union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    else:
      if self.size[x]>=self.size[y]:
        self.parent[y]=x
        self.size[x]+=self.size[y]
      else:
        self.parent[x]=y
        self.size[y]+=self.size[x]
  def cnt(self,x):
    return self.size[self.find(x)]
def main():
  n,m,k=map(int,input().split())
  u=UnionFind(n)
  ans=[0]*n
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.union(a,b)
    ans[a]-=1
    ans[b]-=1
  for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if u.find(c)==u.find(d):
      ans[c]-=1
      ans[d]-=1
  for i in range(n):
    ans[i]+=u.cnt(i)-1
  print(" ".join(map(str,ans)))
main()

Submission status: Accepted

Solution code:
import sys
#input=sys.stdin.readline
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parent=list(range(n))
    self.size=[1]*n
    #print(self.size, end=" self.size \n")
  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 union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    else:
      if self.size[x]>=self.size[y]:
        self.parent[y]=x
        self.size[x]+=self.size[y]
      else:
        self.parent[x]=y
        self.size[y]+=self.size[x]
  def cnt(self,x):
    return self.size[self.find(x)]
def main():
  n,m,k=map(int,input().split())
  u=UnionFind(n)
  ans=[0]*n
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.union(a,b)
    ans[a]-=1
    ans[b]-=1
  for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if u.find(c)==u.find(d):
      ans[c]-=1
      ans[d]-=1
  for i in range(n):
    ans[i]+=u.cnt(i)-1
  print(" ".join(map(str,ans)))
main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x): # find root
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if -self.d[x] < -self.d[y]: # swap
            t = x
            x = y
            y = t
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.d[self.find(x)]
    

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

    deg = [0 for _ in range(N)]
    for _ in range(M): # friends
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        deg[a] += 1
        deg[b] += 1
        uf.unite(a, b)
    # print(uf.d)

    to = [[] for _ in range(N)]
    for _ in range(K): # block
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        to[c].append(d)
        to[d].append(c)

    ret = []
    for i in range(N):
        ans = uf.size(i) - 1 - deg[i]
        for u in to[i]:
            if uf.same(i, u): ans -= 1
        ret.append(str(ans))

    print(' '.join(ret))


main()

Submission status: Accepted

Solution code:

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [-1 for _ in range(n)]
  def find(self, x):
    if self.parent[x] < 0:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]
  def unite(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y:
      return False
    else:
      if self.size(x) < self.size(y):
        x, y = y, x
      self.parent[x] += self.parent[y]
      self.parent[y] = x
      return True
 
  def same(self, x, y):
    return self.find(x) == self.find(y)
  def size(self, x):
    x = self.find(x)
    return -self.parent[x]
  def is_root(self, x):
    return self.parent[x] < 0
 
  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

n,m,k = map(int, input().split())
uf=UnionFind(n)
deg=[0]*n
l=[[] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  deg[a-1]+=1
  deg[b-1]+=1
  uf.unite(a-1,b-1)
for i in range(k):
  c,d = map(int, input().split())
  l[c-1].append(d-1)
  l[d-1].append(c-1)
ans=[]
for i in range(n):
  tmp=uf.size(i)-1-deg[i]
  for u in l[i]:
    if uf.same(i,u):
      tmp-=1
  ans.append(tmp)
print(*ans)