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
from io import StringIO
import unittest
import os


# union find木
# 参考：https://note.nkmk.me/python-union-find/
class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

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

    def members(self, x):
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]
    n, m, k = map(int, input().split())
    friends = [list(map(int, input().split())) for i in range(m)]
    blocks = [list(map(int, input().split())) for i in range(k)]

    # uf 作成(要素数を+1しているのは添え字と人番号を合わせるため)
    uf = UnionFind(n + 1)

    # 除外リスト作成(これは、本問題特有の処理)
    # 添字x: 値yとすると・・ 要素xの友達候補を数えるとき、y(list)に該当する人は除外する。(要素数を+1しているのは添え字と人番号を合わせるため)
    omits = [[] for i in range(n + 1)]

    # UnionFindにて集合を明確にする。
    for friend in friends:
        uf.union(friend[0], friend[1])

        # 除外リストを更新(これは、本問題特有の処理)
        omits[friend[0]].append(friend[1])
        omits[friend[1]].append(friend[0])

    # ブロックリストの情報を除外リストに加える(これは、本問題特有の処理)
    for block in blocks:
        # 同じ集合に属するウ場合のみ、リストに追加
        if uf.is_same(block[0], block[1]):
            omits[block[0]].append(block[1])
            omits[block[1]].append(block[0])

    # 友達候補数を出力して終了(人は1始まりなので1からループを行う
    # ans = []
    # for i in range(1, n + 1):
        # 友達候補 = 集合数 - 除外リスト(自分の友人数 + 自分がブロックしている人数) - 1(集合に含まれる自分自身を除く)
    #     ans.append(uf.size(i) - len(omits[i]) - 1)
    # print(" ".join(ans))

    # ans = [str(uf.size(i) - len(omits[i]) - 1) for i in range(1, n + 1)]
    ans = [uf.size(i) - len(omits[i]) - 1 for i in range(1, n + 1)]

    print(*ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os


# union find木
# 参考：https://note.nkmk.me/python-union-find/
class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

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

    def members(self, x):
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]
    n, m, k = map(int, input().split())
    friends = [list(map(int, input().split())) for i in range(m)]
    blocks = [list(map(int, input().split())) for i in range(k)]

    # uf 作成(要素数を+1しているのは添え字と人番号を合わせるため)
    uf = UnionFind(n + 1)

    # 除外リスト作成(これは、本問題特有の処理)
    # 添字x: 値yとすると・・ 要素xの友達候補を数えるとき、y(list)に該当する人は除外する。(要素数を+1しているのは添え字と人番号を合わせるため)
    omits = [[] for i in range(n + 1)]

    # UnionFindにて集合を明確にする。
    for friend in friends:
        uf.union(friend[0], friend[1])

        # 除外リストを更新(これは、本問題特有の処理)
        omits[friend[0]].append(friend[1])
        omits[friend[1]].append(friend[0])

    # ブロックリストの情報を除外リストに加える(これは、本問題特有の処理)
    for block in blocks:
        # 同じ集合に属するウ場合のみ、リストに追加
        if uf.is_same(block[0], block[1]):
            omits[block[0]].append(block[1])
            omits[block[1]].append(block[0])

    # 友達候補数を出力して終了(人は1始まりなので1からループを行う
    # ans = []
    # for i in range(1, n + 1):
        # 友達候補 = 集合数 - 除外リスト(自分の友人数 + 自分がブロックしている人数) - 1(集合に含まれる自分自身を除く)
    #     ans.append(uf.size(i) - len(omits[i]) - 1)

    ans = [str(uf.size(i) - len(omits[i]) - 1) for i in range(1, n + 1)]

    print(" ".join(ans))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

N, M, K = map(int, readline().split())
u = UnionFind(N + 1)
friends_cnt = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, readline().split())
    u.unite(a, b)
    friends_cnt[a] += 1
    friends_cnt[b] += 1
for i in range(K):
    c, d = map(int, readline().split())
    if u.is_same(c, d):
        friends_cnt[c] += 1
        friends_cnt[d] += 1

for i in range(1, N + 1):
    print(u.get_size(i) - friends_cnt[i] - 1)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os


# union find木
# 参考：https://note.nkmk.me/python-union-find/
class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

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

    def members(self, x):
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]
    n, m, k = map(int, input().split())
    friends = [list(map(int, input().split())) for i in range(m)]
    blocks = [list(map(int, input().split())) for i in range(k)]

    # uf 作成(要素数を+1しているのは添え字と人番号を合わせるため)
    uf = UnionFind(n + 1)

    # 除外リスト作成(これは、本問題特有の処理)
    # 添字x: 値yとすると・・ 要素xの友達候補を数えるとき、y(list)に該当する人は除外する。(要素数を+1しているのは添え字と人番号を合わせるため)
    omits = [[] for i in range(n + 1)]

    # UnionFindにて集合を明確にする。
    for friend in friends:
        uf.union(friend[0], friend[1])

        # 除外リストを更新(これは、本問題特有の処理)
        omits[friend[0]].append(friend[1])
        omits[friend[1]].append(friend[0])

    # ブロックリストの情報を除外リストに加える(これは、本問題特有の処理)
    for block in blocks:
        # 同じ集合に属するウ場合のみ、リストに追加
        if uf.is_same(block[0], block[1]):
            omits[block[0]].append(block[1])
            omits[block[1]].append(block[0])

    # 友達候補数を出力して終了(人は1始まりなので1からループを行う
    ans = []
    for i in range(1, n + 1):
        # 友達候補 = 集合数 - 除外リスト(自分の友人数 + 自分がブロックしている人数) - 1(集合に含まれる自分自身を除く)
        ans.append(str(uf.size(i) - len(omits[i]) - 1))

    print(" ".join(ans))

# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from collections import deque
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)


# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N

for root in range(N):
    cnt = 0
    if visited[root]:
        continue

    # D[root] = set([root])
    # 訪問先のスタック
    stack = [root]
    # 訪問先が無くなるまで
    while stack:
        # 訪問者をポップアップ
        n = stack.pop()
        # 訪問者を訪問済み
        if visited[n]:
            continue
        visited[n] = True
        cnt +=1
        # 訪問者のグループの親を設定
        parent[n] = root

        # root のフレンドをグループと訪問先に追加
        for to in F[n]:
            if visited[to]:
                continue
            # D[root].add(to)
            stack.append(to)
    if cnt!=0:
        D[root]=cnt
# print(D)
ans = [0]*N
for iam in range(N):
    # group = gro[parent[iam]]
    tmp_ans = D[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(F[iam])
    for block in B[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    # if alre[i]==True:
    #     continue
    # gro[i]=set([i])
    y.append(i)
    leader = i
    cnt = 0 
    while len(y)>0:
        x = y.popleft()
        if parent[x]!=-1:
            continue
            # print(to)
        parent[x]=leader
        y.extend(cango[x])
        cnt +=1
    if cnt!=0:
        gro[leader]=cnt
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    # group = gro[parent[iam]]
    tmp_ans = gro[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(cango[iam])
    for block in cannotgo[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
import sys
f=lambda:tuple(map(int,sys.stdin.readline().split()))
n,m,k=f()
lta=[f() for _ in range(m)]
ltb=[f() for _ in range(k)]
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=[0]*n
for a,b in lta:
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for c,d in ltb:
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
for i in range(n):
  l[i]+=size(i)-1
print(*l)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, K, ABs, CDs):
    friend_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        friend_map[a].append(b)
        friend_map[b].append(a)

    block_map = [[] for _ in range(N + 1)]
    for c, d in CDs:
        block_map[c].append(d)
        block_map[d].append(c)

    def dfs(group_num, members, now_n):
        belongs[now_n] = group_num
        members.append(now_n)
        for f in friend_map[now_n]:
            if belongs[f] == -1:
                members = dfs(group_num, members, f)
        return members

    friend_groups = []
    belongs = [-1] * (N + 1)
    for i in range(1, N + 1):
        if belongs[i] == -1:
            m = dfs(len(friend_groups), [], i)
            m.sort()
            friend_groups.append(m)

    ans = ''
    for n in range(1, N + 1):
        block = 0
        group = friend_groups[belongs[n]]
        for b in block_map[n]:
            if belongs[n] == belongs[b]:
                block += 1
        ans += ' ' + str(len(group) - len(friend_map[n]) - block - 1)
    print(ans[1:])


if __name__ == '__main__':
    # # handmade test
    # N, M, K = 2 * 10 ** 5, 10 ** 5, 10 ** 5
    # ABs = [[1, i] for i in range(2, 10 ** 5 + 2)]
    # CDs = [[i, i + 1] for i in range(2, 10 ** 5 + 2)]
    
    # # handmade random
    # import random
    # N, M, K = 20, 10, 10
    # ABs = []
    # while True:
    #     if len(ABs) == M:
    #         break
    #     a = random.randint(1, N - 1)
    #     b = random.randint(a + 1, N)
    #     if not [a, b] in ABs:
    #         ABs.append([a, b])
    # CDs = []
    # while True:
    #     if len(CDs) == K:
    #         break
    #     c = random.randint(1, N - 1)
    #     d = random.randint(c + 1, N)
    #     if not [c, d] in ABs and not [c, d] in CDs:
    #         CDs.append([c, d])
    # print(N, M, K)
    # print(ABs)
    # print(CDs)

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

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10 ** 6)
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, K, ABs, CDs):
    friend_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        friend_map[a].append(b)
        friend_map[b].append(a)

    block_map = [[] for _ in range(N + 1)]
    for c, d in CDs:
        block_map[c].append(d)
        block_map[d].append(c)

    # print('friend_map')
    # for i in range(len(friend_map)):
    #     print(friend_map[i])
    #
    # print('block_map')
    # for i in range(len(block_map)):
    #     print(block_map[i])

    def dfs(group_num, members, now_n):
        belongs[now_n] = group_num
        members.append(now_n)
        for f in friend_map[now_n]:
            if belongs[f] == -1:
                members = dfs(group_num, members, f)
        return members

    friend_groups = []
    belongs = [-1] * (N + 1)
    for i in range(1, N + 1):
        if belongs[i] == -1:
            m = dfs(len(friend_groups), [], i)
            m.sort()
            friend_groups.append(m)

    # print('friend_groups')
    # for i in range(len(friend_groups)):
    #     print(friend_groups[i])

    # print('belongs')
    # print(belongs)
    ans = ''
    for n in range(1, N + 1):
        block = 0
        group = friend_groups[belongs[n]]
        for b in block_map[n]:
            # if bisect.bisect_left(group, b) >= len(group):
            #     print(group)
            #     print(n, b)
            #     input()
            x = bisect.bisect_left(group, b)
            # if x < len(group) and b == group[x]:
            #     block += 1
            if belongs[n] == belongs[b]:
                block += 1
        # print('n', n, 'friend_num', len(friend_map[n]), 'block_num', block)
        ans += ' ' + str(len(group) - len(friend_map[n]) - block - 1)
    print(ans[1:])


if __name__ == '__main__':
    # # handmade test
    # N, M, K = 2 * 10 ** 5, 10 ** 5, 10 ** 5
    # ABs = [[1, i] for i in range(2, 10 ** 5 + 2)]
    # CDs = [[i, i + 1] for i in range(2, 10 ** 5 + 2)]
    # while True:
    #     import random
    #     N, M, K = 20, 10, 10
    #     ABs = []
    #     while True:
    #         if len(ABs) == M:
    #             break
    #         a = random.randint(1, N - 1)
    #         b = random.randint(a + 1, N)
    #         if not [a, b] in ABs:
    #             ABs.append([a, b])
    #     CDs = []
    #     while True:
    #         if len(CDs) == K:
    #             break
    #         c = random.randint(1, N - 1)
    #         d = random.randint(c + 1, N)
    #         if not [c, d] in ABs and not [c, d] in CDs:
    #             CDs.append([c, d])
    #     print(N, M, K)
    #     print(ABs)
    #     print(CDs)
    #     solve(N, M, K, ABs, CDs)

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

Submission status: Accepted

Solution code:
# Union-Find
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
    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())
Friend = [[] for _ in range(N)]

par = [-1] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)
    Friend[a].append(b)
    Friend[b].append(a)

Block = [[] for _ in range(N)]
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):
    ans = size(i) - 1
    ans -= len(Friend[i])
    for b in Block[i]:
        if same(i, b):
            ans -= 1
    Ans.append(str(ans))

print(' '.join(Ans))

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):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根(最初は全て根)
        self.par = [i for i in range(n)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * n
        # 人間の数
        self.size = [1] * n

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら、親の要素で再検索
        else:
            # 走査していく過程で親を書き換える(return xが代入される)
            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]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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:
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):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根(最初は全て根)
        self.par = [i for i in range(n)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * n
        # 人間の数
        self.size = [1] * n

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら、親の要素で再検索
        else:
            # 走査していく過程で親を書き換える(return xが代入される)
            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]
            # 木の高さが同じなら片方を1増やす
            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 sys import setrecursionlimit
setrecursionlimit(10 ** 5)

def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j

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

parent = [-1] * n
friends = [[] for _ in range(n)]

for a, b in ab:
    unite(parent, a-1, b-1)
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
    
blocks = [[] for _ in range(n)]
for c, d in cd:
    blocks[c-1].append(d-1)
    blocks[d-1].append(c-1)

result = []

for i in range(n):
    p = find(parent, i)
    t = -parent[p] - 1
    t -= len(friends[i])
    for b in blocks[i]:
        if p == find(parent, b):
            t -= 1
    result.append(t)
    
print(*result)