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(10**9)

n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [[] for i in range(n)]
l = [0]*n

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

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

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

for i in range(n):
    if seen[i] == 0:
        r.append(set())
        dfs(i)
        cnt += 1

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & set(B[j])) - 1

print(*ans)

Submission status: Accepted

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

n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [set() for i in range(n)]
l = [0]*n

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

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

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

for i in range(n):
    if seen[i] == 0:
        r.append(set())
        dfs(i)
        cnt += 1

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & B[j]) - 1

print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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


def solve():
    N, M, K = Scanner.map_int()
    uni = UnionFind(N)
    friends = [set() for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        uni.unite(a, b)
        friends[a].add(b)
        friends[b].add(a)
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        block[a].add(b)
        block[b].add(a)
    ans = [0 for _ in range(N)]
    for i in range(N):
        size = uni.size(i)
        f = len(friends[i])
        bn = 0
        for b in block[i]:
            if uni.is_same(i, b):
                bn += 1
        ans[i] = size - 1 - f - bn
    print(*ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6 + 10)

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)]
group = []  # 連結成分ごとのサイズ
person_group = [-1] * n  # 人ごとの属するグループ
person_unable= [0] * n  # 人ごとの候補に入らない人の人数
graph = [[] for _ in range(n)]  # 連結リスト
for ab in AB:
    ab[0] -= 1
    ab[1] -= 1
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])

seen = [False] * n
# その節の連結成分のサイズを返す
def dfs(n, group_id):
    global size
    seen[n] = True
    person_group[n] = group_id
    for v in graph[n]:
        if seen[v]:
            continue
        size = dfs(v, group_id)
    size += 1
    return size
    
    
group_id = 0
for i in range(n):
    if seen[i]:
        continue
    size = 0
    group.append(dfs(i, group_id))
    group_id += 1

# unable計算。まず友達の人
for i in range(n):
    person_unable[i] += len(graph[i])
# 次にブロックの人
for i in range(k):
    CD[i][0] -= 1
    CD[i][1] -= 1
    if person_group[CD[i][0]] == person_group[CD[i][1]]:
        person_unable[CD[i][0]] += 1
        person_unable[CD[i][1]] += 1

for i in range(n):
    print(group[person_group[i]] - person_unable[i] - 1, "", end="")

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()

Submission status: Accepted

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

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

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
    
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]

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

friend = [0]*(n+1)
for i in range(m):
    friend[ab[i][1]] += 1
    friend[ab[i][0]] += 1

par = [-1]*(n+1)
for i in range(m):
    unite(ab[i][0],ab[i][1])

block = [0]*(n+1)
for i in range(k):
    if same(cd[i][0],cd[i][1]):
        block[cd[i][0]] += 1
        block[cd[i][1]] += 1
    #block[cd[i][0]].append(cd[i][1])
    #block[cd[i][1]].append(cd[i][0])



for i in range(1,n+1):
    print(size(i)-friend[i]-block[i]-1,end = " ")

Submission status: Accepted

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

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

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

Block = [set() for i in range(N)]
for _ in range(K):
  C, D = map(int, input().split())
  Block[C-1].add(D-1)
  Block[D-1].add(C-1)


def dfs(x):
    if seen[x] == 0:
        R[cnt].add(x)
        seen[x]=1
        for i in Friend[x]:
            dfs(i)

seen = [0]*N
cnt  = 0
R    = []
for i in range(N):
    if seen[i] == 0:
        R.append(set())
        dfs(i)
        cnt += 1

seq = [0]*N

for r in R:
    lr = len(r)
    for j in r:
        seq[j] = lr - len(Friend[j]) - len(r&Block[j]) - 1

print(*seq)

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)


n, m, k = map(int, input().split())
u = UnionFind(n + 1)
already = [0] * (n + 1)

for i in range(m):
    a, b = map(int, input().split())
    u.union(a, b)
    already[a] += 1
    already[b] += 1
for i in range(k):
    c, d = map(int, input().split())
    if u.same(c, d):
        already[c] += 1
        already[d] += 1

for i in range(1, n + 1):
    print(u.size(i) - already[i] - 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

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


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)

Submission status: Accepted

Solution code:
N, M, K=map(int,input().split())
AB=[list(map(int,input().split()))for _ in range(M)]
CD=[list(map(int,input().split()))for _ in range(K)]
import sys;sys.setrecursionlimit(10**9)
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())
u=UnionFind(N)
for a,b in AB:u.union(a-1,b-1)
ans=[u.size(i)-1 for i in range(N)]

for a,b in AB:
  if u.same(a-1,b-1):
    ans[a-1]-=1
    ans[b-1]-=1
for c,d in CD:
  if u.same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
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
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

U = UnionFind(N+1)
frendlist = [0]*(N+1)
blocklist = [0]*(N+1)
for _ in range(M):
    A, B = map(int,input().split())
    frendlist[A] +=1
    frendlist[B] +=1
    U.union(A,B)

for _ in range(K):
    C, D = map(int,input().split())
    if U.same(C,D):
        blocklist[C] +=1
        blocklist[D] +=1

for i in range(1,N+1):
    print(U.size(i)-1 -frendlist[i]-blocklist[i],end=" ")

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y: return False
    #sizeの大きいほうがx
    if par[x] > par[y]: x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
enemy = [[] for _ in range(n)]
par = [-1]*n


for _ in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(k):
    a, b = map(int, input().split())
    enemy[a-1].append(b-1)
    enemy[b-1].append(a-1)
ans = []
for i in range(n):
    block = 0
    for j in enemy[i]:
        if same(i, j): block += 1
    ans.append(size(i)-len(friend[i])-block-1)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    #https://note.nkmk.me/python-union-find/ 
    #note.nkmk.me  2019-08-18 
    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())


#初期入力、集合とユニオンファインド
import sys
input = sys.stdin.readline
N,M,K = (int(x) for x in input().split())

#接続（友好関係、ブロック関係）
uf =UnionFind(N+1)
conn_fri ={i:set() for i in range(1,N+1)}
conn_blo ={i:set() for i in range(1,N+1)}
for i in range(M):
    a,b = (int(x) for x in input().split())
    uf.union(a,b)
    conn_fri[a].add(b)
    conn_fri[b].add(a)
for i in range(K):
    c,d = (int(x) for x in input().split())
    conn_blo[c].add(d)
    conn_blo[d].add(c)

#友達候補の数＝同じグループにいる、友達関係でない、ブロック関係でない
ans ={i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    root =uf.find(i)
    all =uf.size(root)
    same_groop_block =0
    for j in conn_blo[i]:
        if uf.same(i,j): #同じグループにいるけどブロック関係
            same_groop_block +=1
    ans[i] =all -len(conn_fri[i]) -same_groop_block -1 #-1 自分を引く

#出力
print(*ans.values())
#print(all)

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, M ,K = map(int, input().split())
UF = UnionFind(N)
ans = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    UF.union(a-1, b-1)
    ans[a-1] -= 1
    ans[b-1] -= 1  
for i in range(K):
    a, b = map(int, input().split())
    if UF.same(a-1, b-1):
        ans[a-1] -= 1
        ans[b-1] -= 1   
for i in range(N):
    ans[i] += UF.size(i)-1
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(150000)

n,m,k = map(int, input().split())
f_G = defaultdict(lambda:[])
b_G = defaultdict(lambda:[])

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

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

def dfs(graph,v,cnt,list):
    global node
    seen[v] = True
    node += 1

    for nv in f_G[v]:
        if seen[nv]:
            continue
        dfs(graph,nv,cnt,list)

    list[v] = cnt

d = [0]
list = [0] * n
seen = [False] * n
cnt = 0
for i in range(n):
    if seen[i]:
        continue
    cnt += 1
    node = 0
    dfs(f_G,i,cnt,list)
    d.append(node)

ans = [0] * n
for i in range(n):
    a = d[list[i]]
    a -= (len(f_G[i]) + 1)

    for j in (b_G[i]):
        if list[i] == list[j]:
            a -= 1

    ans[i] = a

print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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


n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
block = [[] for _ in range(n)]
uf = Uf(n)
F = [list(map(int, input().split())) for _ in range(m)]
B = [list(map(int, input().split())) for _ in range(k)]

for e in F:
    friends[e[0] - 1].append(e[1] - 1)
    friends[e[1] - 1].append(e[0] - 1)
    uf.unite(e[0]-1, e[1]-1)

for e in B:
    block[e[0] - 1].append(e[1] - 1)
    block[e[1] - 1].append(e[0] - 1)

ans = [0]*n
for i in range(n):
    ans[i] = uf.size[uf.root(i)] - 1
    for f in friends[i]:
        if uf.same(i, f):
            ans[i] -= 1
    for b in block[i]:
        if uf.same(i, b):
            ans[i] -= 1

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
to = [0 for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
    to[a] += 1
    to[b] += 1
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        cou = 1
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
                    cou += 1
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i][0]:
        ans[j-1] = len(kurasuta[i][0]) - to[j] - 1 - len(kurasuta[i][0] & bro[j])

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
to = [0 for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
    to[a] += 1
    to[b] += 1
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        cou = 1
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
                    cou += 1
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i][0]:
        ans[j-1] = kurasuta[i][1] - to[j] - 1 - len(kurasuta[i][0] & bro[j])

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

LI = lambda: list(map(int, input().split()))

n, m, k = LI()
adj = [[] for i in range(n)]
for i in range(m):
    a, b = LI()
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
c = []
d = []
for i in range(k):
    tmp = LI()
    c.append(tmp[0]-1)
    d.append(tmp[1]-1)

cc = [i for i in range(n)]
num = [0 for i in range(n)]
for i in range(n):
    if cc[i] == i:
        dq = deque([i])
        while dq:
            j = dq.popleft()
            for l in adj[j]:
                if cc[l] != i:
                    cc[l] = i
                    num[i] += 1
                    dq.append(l)

sf = []
for i in range(n):
    sf.append(num[cc[i]])

for i in range(n):
    sf[i] -= len(adj[i])

for i in range(k):
    if cc[c[i]] == cc[d[i]]:
        sf[c[i]] -= 1
        sf[d[i]] -= 1

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

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
    #木の深さじゃなくxを含む集合の要素数
    def size(self,x):
        return -self.parents[self.find(x)]

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

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

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

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

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

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

n,m,k= map(int,input().split())
u = UnionFind(n+1)
atodehiku = [0]*(n+1)

for i in range(m):
    a,b = map(int,input().split())
    u.union(a,b)
    atodehiku[a]+=1
    atodehiku[b]+=1
for i in range(k):
    c,d = map(int,input().split())
    if u.same(c,d):
        atodehiku[c]+=1
        atodehiku[d]+=1

for i in range(1,n+1):
    print(u.size(i)-atodehiku[i]-1)