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 collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


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

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

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

  num_cand = [-1]*(N)
  member = {}
  group = {}

  for i in range(N):
    if i in group:
      continue
    start = i
    # print(f'start:{start}')
    q = deque([start])
    member[start] = set([start])
    group[start] = start
    is_visited = set([start])
    while len(q):
      now = q.popleft()
      for next_ in friends[now]:
        num_cand[now] -= 1
        # print(f'group:{start}, now:{now}->next_:{next_}', now, '-1')
        if next_ not in is_visited:
          member[start].add(next_)
          group[next_] = start
          # num_cand[next_] -= 1
          # print(f'group:{start}, now:{now}->next_:{next_}', next_, '-1')
          # num_cand[now] -= 1
          # print(f'group:{start}, now:{now}->next_:{next_}', now, '-1')
          q.append(next_)
          is_visited.add(next_)

  # print(member)
  # print(num_cand)
  for i in range(N):
    num_cand[i] += len(member[group[i]])
    for enemy in block[i]:
      if enemy in member[group[i]]:
        num_cand[i] -= 1

  print(*num_cand, sep=' ')


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
        group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])

Submission status: Accepted

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

friend = [[] for i in range(n)]
block = [[] for i in range(n)]

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)

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

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

ans=[]

for i in range(n):
    ans1 = uf.size(i)-1
    for j in block[i]:
        if uf.same(i,j):
            ans1-=1
    ans1 -= len(friend[i])
    ans.append(str(ans1))

print(' '.join(ans))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m,k=f()

# Union_Find
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

l=[-1]*n
for _ in range(m):
  a,b=f()
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for i in range(n):
  l[i]+=size(i)
for _ in range(k):
  c,d=f()
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
print(*l)

Submission status: Accepted

Solution code:
from collections import deque

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

f = [set() for _ in range(N + 1)]
b = [set() for _ in range(N + 1)]

for i, j in friend:
    f[i].add(j)
    f[j].add(i)
for i, j in block:
    b[i].add(j)
    b[j].add(i)

stack = deque()
ans = [0] * (N + 1)
visited = [0] * (N + 1)

for i in range(1, N + 1):
    if visited[i]:
        continue
    # setは{}で書く
    link = {i}
    stack.append(i)
    visited[i] = 1
    while stack:
        n = stack.pop()
        # nのフレンド全員について
        for j in f[n]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                # link(set)に追加
                link.add(j)
    for i in link:
        # 全体-既にフレンドの人数-ブロックした人数-自分自身
        # set同士で積集合をとる
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1

print(*ans[1:])

Submission status: Accepted

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

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n, m, k = map(int, input().split())
friend = [set() for _ in range(n)]
block = [set() for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    friend[a - 1].add(b - 1)
    friend[b - 1].add(a - 1)
for _ in range(k):
    a, b = map(int, input().split())
    block[a - 1].add(b - 1)
    block[b - 1].add(a - 1)
visited = [0 for _ in range(n)]
ans = [None for _ in range(n)]
for i in range(n):
    if visited[i]:
        continue
    prefriends = {i}
    check = deque([i])
    while check:
        now = check.pop()
        visited[now] = 1
        for next in friend[now]:
            if visited[next] == 0:
                check.append(next)
                prefriends.add(next)
    for j in prefriends:
        ans[j] = len(prefriends) - 1 - len(friend[j]) - len(prefriends & block[j])
print(' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

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

    def friend_candidate(self):
        tbl = self.table
        n = len(tbl)
        candidates = [0] * n
        root = [-1] * n
        for i, parent in enumerate(tbl):
            if parent >= 0:
                root[i] = self._root(parent)
                candidates[root[i]] += 1
        for i in range(n):
            if tbl[i] >= 0:
                candidates[i] = candidates[root[i]]
        return candidates


def main():
    input = sys.stdin.buffer.readline
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    num_friends = [0] * n
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
        num_friends[a] += 1
        num_friends[b] += 1
    num_block = [0] * n
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.find(c, d):
            num_block[c] += 1
            num_block[d] += 1
    fc = uf.friend_candidate()
    ans = [0] * n
    for i in range(n):
        ans[i] = fc[i] - num_friends[i] - num_block[i]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import Counter

def dfs(nw):
    for nx in F[nw]:
        if V[nx]==-1:
            V[nx] = cnt
            dfs(nx)

n, m, k = list(map(int, sys.stdin.readline().split()))
F = [[] for _ in range(n)]
B = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[a].append(b)
    F[b].append(a)
for i in range(k):
    c,d = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    B[c].append(d)
    B[d].append(c)

V = [-1]*n
cnt = 1
for i in range(n):
    if V[i]==-1:
        V[i] = cnt
        dfs(i)
        cnt += 1
cV = Counter(V)
ans = []
for i in range(n):
    ans.append(cV[V[i]]-1 - len(F[i]) - sum([V[b]==V[i] for b in B[i]]))

print(*ans)

Submission status: Accepted

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

import sys
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def graph_input(N, M):
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, readline().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return G


friend = graph_input(N, M)
block = graph_input(N, K)
seen = [0] * N


def dfs(x, group):
    # DFS で頂点 x がどの group に属するかを記録していく
    # 後に、各 group に対して、seen[x] = group となるがいくつあるか数えれば連結成分数もわかる
    seen[x] = group
    for y in friend[x]:
        if seen[y]:
            continue
        else:
            seen[y] = group
            dfs(y, group)


group = 1
for x in range(N):
    if seen[x] == 0:
        dfs(x, group)
        group += 1


counter = Counter(seen)  # リストの値の出現回数を Counter で数えることで各連結成分数を得ている

res = []
for x in range(N):
    # x 自身を連結成分数から除く-1 さらに friend[x] を除く
    cand_n = counter[seen[x]] - len(friend[x]) - 1
    # block[x]と xの連結成分の共通部分の抜くのが難しい
    for a in block[x]:
        if seen[a] == seen[x]:
            cand_n -= 1
    res.append(cand_n)

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


if __name__ == '__main__':
    print()

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


friends = UnionFind(n)
direct_friends = [0] * n
enemies = [[] for _ in range(n)]

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

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

ans = []
for i in range(n):
    num = friends.size(i) - 1 - direct_friends[i]
    for enm in enemies[i]:
        if friends.same(i, enm):
            num -= 1
    ans.append(num)

print(*ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
f = [[] for _ in range(n)]
g = [[] 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
    g[c].append(d)
    g[d].append(c)
d = {}
parent = [-1]*n
seen = [False]*n
from collections import deque
for i in range(n):
    if seen[i]: continue
    stack = deque()
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        parent[v]=i
        for nv in f[v]:
            if seen[nv]: continue
            d[i].add(nv)
            stack.append(nv)
ans = [0]*n
for i in range(n):
    group = d[parent[i]]
    sum = len(group) -len(f[i]) - len(set(g[i])&group) -1
    ans[i]=sum
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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):
        """
        yをxの根に繋ぐ
        """
        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):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
        uf.union(a - 1, b - 1)

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

    res = []
    for i in range(n):
        cnt = uf.size(i) - len(edge[i]) - 1
        for j in block[i]:
            if uf.same(i, j):
                cnt -= 1
        res.append(cnt)
    print(*res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
        self._table[x] += self._table[y]
        self._table[y] = x
    
    def same(self, x, y):
        return self._root(x) == self._root(y)

    def count_members(self, x):
        return -self._table[self._root(x)]
    
    def count_groups(self):
        return len({self._root(i) for i in range(n)})
    
    def __str__(self):
        return str([self._root(i) for i in range(n)])
    
    def __repr__(self):           
        return repr([self._root(i) for i in range(n)])

n, m, k, *ABCD = map(int, open(0).read().split())
AB = zip(ABCD[:2*m][::2], ABCD[:2*m][1::2])
CD = zip(ABCD[2*m:][::2], ABCD[2*m:][1::2])

uf = UnionFind(n)

friends = [set() for _ in range(n)]
for a, b in AB:
    a, b = a-1, b-1
    uf.unite(a, b)
    friends[a].add(b)
    friends[b].add(a)
    
blocks = [set() for _ in range(n)]
for c, d in CD:
    c, d = c-1, d-1
    if uf.same(c, d):
        blocks[c].add(d)
        blocks[d].add(c)

candidates = []
for i in range(n):
    candidates.append(uf.count_members(i)-len(friends[i])-len(blocks[i])-1)
print(*candidates)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
f = [[] for _ in range(n)]
g = [[] 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
    g[c].append(d)
    g[d].append(c)
d = {}
parent = [-1]*n
seen = [False]*n
from collections import deque
for i in range(n):
    if seen[i]: continue
    stack = deque()
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        parent[v] = i #同じ連結成分をまとめる
        seen[v] = True
        for nv in f[v]:
            if seen[nv]: continue
            d[i].add(nv)
            stack.append(nv)
ans = [0]*n
for i in range(n):
    group = d[parent[i]]
    #連結成分-直接の友達関係-ブロックしてるけど連結成分にいる人-自分
    sum = len(group)-len(f[i])-len(set(g[i])&group) -1
    ans[i] = sum
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())
uf = UnionFind(n)
fs = [[] for _ in range(n)]
bs = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    uf.union(a, b)
    fs[a].append(b)
    fs[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    bs[c].append(d)
    bs[d].append(c)

for i in range(n):
    ans = uf.size(i)
    ans -= 1 + len(fs[i])
    for b in bs[i]:
        if uf.same(i, b):
            ans -= 1
    print(ans, end=' ')

Submission status: Accepted

Solution code:
class UnionFind():
    
    # 要素数を指定して作成 はじめは全ての要素が別グループに属し、親はいない
    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]:  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)]
    
    # ｘとyが同じグループか否か
    def same(self, x, y):  return self.find(x) == self.find(y)
    
    # xと同じメンバーの要素
    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())
    
    # 可視化 [print(uf)]
    def __str__(self):  return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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

G2 = [[] for _ in range(N)]
for i in range(K):
    a, b = map(int, input().split())
    G2[a - 1].append(b - 1)
    G2[b - 1].append(a - 1)
    
uf = UnionFind(N)
for i in range(N):
    for j in G1[i]:
        uf.union(i, j)
    
for i in range(N):
    ans = uf.size(i)  - len(G1[i]) - 1
    for j in G2[i]:
        if uf.same(i, j):  ans -= 1
    print(ans)

Submission status: Accepted

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

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])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする（出来るだけ浅い木にするため）
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

    def size(self, x):                                          # xの根のparent（= 要素数）を返す
        return -self.parents[self.find(x)]

    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):                                          # print(self) での返し方を定義
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


##############################################################################################################

V, E, K = map(int, input().split())                            # V: 頂点数　E: 辺の数

tree = UnionFind(V)

edges = [[] for _ in range(V)]
for _ in range(E):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree.union(a, b)
    edges[a].append(b)
    edges[b].append(a)


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

res = []
for x in range(V):
    n = tree.size(x)
    temp = n-1
    for y in edges[x]:
        if tree.same(x,y):
            temp -= 1
    for y in blocks[x]:
        if tree.same(x,y):
            temp -= 1
    res.append(temp)

print(*res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5) #再帰回数を増やさないとREになる

N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ 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)
for _ in range(K):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)

sgn = [0 for _ in range(N)]
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] == 0:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)

count = [0 for _ in range(groupnum)]
for k in range(N):
  count[sgn[k]-1] += 1

ans = ''
for k in range(N):
  num = count[sgn[k]-1] -1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans += str(num) + ' '

ans.rstrip()
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) #再帰回数を増やさないとREになる


N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ 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)
for _ in range(K):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)


friendnetwork = []
sgn = [0 for _ in range(N)] #groupnumを書いていく
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)


friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = []
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans.append(num)

for j in range(len(ans)):
  print(ans[j])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ 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)
for _ in range(K):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)


friendnetwork = []
sgn = [0 for _ in range(N)]
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)


friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = []
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans.append(num)

a = str(ans[0])
for j in range(1, len(ans)):
  a += ' '+ str(ans[j])
print(a)