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: Time Limit Exceeded

Solution code:
# D 解き直し
# Union Find
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())
friend = [[False for j in range(n)] for i in range(n)]
block = [[False for j in range(n)] for i in range(n)]
ans = [0 for i in range(n)]
unions = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    friend[a-1][b-1] = True
    friend[b-1][a-1] = True
    unions.union(a-1, b-1)
for i in range(k):
    a,b = map(int, input().split())
    block[a-1][b-1] = True
    block[b-1][a-1] = True
for i in range(n):
    ms = unions.members(i)
    count = 0
    for m in ms:
        if not(block[i][m] or friend[i][m]):
            count += 1
    ans[i] = count -1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# D 解き直し
# Union Find
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())
friend = [[] for i in range(n)]
block = [[] for i in range(n)]
ans = [0 for i in range(n)]
unions = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    unions.union(a-1, b-1)
for i in range(k):
    a,b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(n):
    ms = unions.members(i)
    count = 0
    for m in ms:
        if not(m in friend[i] or m in block[i]):
            count += 1
    ans[i] = count -1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
#import collections
import sys

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

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, m, k = list(map(int,ipti().split()))
    r = UnionFind(n)
    rr = [set() for _ in range(n)]

    for i in range(m):
        a, b = list(map(int,ipti().split()))
        a, b = a-1, b-1
        r.union(a, b)
        rr[a].add(b)
        rr[b].add(a)

    for i in range(k):
        a, b = list(map(int,ipti().split()))
        a, b = a-1, b-1
        rr[a].add(b)
        rr[b].add(a)

    ans = [0] * n

    for i in range(n):
        ans[i] = len((set(r.members(i)) - rr[i])) - 1

    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import collections
import sys

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

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, m, k = list(map(int,ipti().split()))
    r = UnionFind(n)
    rr = [set() for _ in range(n)]

    for i in range(m):
        a, b = list(map(int,ipti().split()))
        a, b = a-1, b-1
        r.union(a, b)
        rr[a].add(b)
        rr[b].add(a)

    for i in range(k):
        a, b = list(map(int,ipti().split()))
        a, b = a-1, b-1
        rr[a].add(b)
        rr[b].add(a)

    ans = [0] * n

    for i in range(n):
        rp = set(r.members(i))
        ans[i] = len(rp - rr[i]) - 1

    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M, K = map(int, input().split())
friend_relationships = []
blocked_relationships = []
adjecency_list = [[i] for i in range(N)]
list_of_candidates_num = []

for i in range(M):
    l = list(map(int, input().split()))
    friend_relationships.append(l)

for i in range(K):
    l = list(map(int, input().split()))
    blocked_relationships.append(l)

for relationship in friend_relationships:
    adjecency_list[relationship[0]-1].append(relationship[1]-1)
    adjecency_list[relationship[1]-1].append(relationship[0]-1)

def breadth_first_search(input_adjecency_list):
    num_of_nodes = len(input_adjecency_list)
    work_queue = deque([])
    will_visit = set(list(range(num_of_nodes)))
    visiting = set()
    visited = set()
    output_list = [[] for i in range(num_of_nodes)]

    while will_visit:
        s = will_visit.pop()
        work_queue.append(s)

        while work_queue:
            here = work_queue.popleft()

            if here in visited: continue

            for node in input_adjecency_list[here]:
                work_queue.append(node)
                visiting.add(node)
                visited.add(here)

        for i in list(visiting):
            output_list[i]= set(list(visiting))

        visiting.clear()
        will_visit = will_visit - visited

    return output_list

def candidates_choice(input_graph, input_friends, input_blocked):
    num_of_nodes = len(input_graph)
    output_graph = input_graph

    for relationship in input_friends:
        output_graph[relationship[0]-1].discard(relationship[1]-1)
        output_graph[relationship[1]-1].discard(relationship[0]-1)

    for relationship in input_blocked:
        output_graph[relationship[0]-1].discard(relationship[1]-1)
        output_graph[relationship[1]-1].discard(relationship[0]-1)

    for self_node in range(num_of_nodes):
        output_graph[self_node].discard(self_node)

    return output_graph

graph = breadth_first_search(adjecency_list)
candidates_graph = candidates_choice(graph, friend_relationships, blocked_relationships)
for i in range(N):
    list_of_candidates_num.append(len(candidates_graph[i]))

"""
print(adjecency_list)
print(graph)
print(candidates_graph)
"""

print(*list_of_candidates_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = [None for n in nodes]
        self.sizes = [1 for n in nodes]

    def find(self, a):
        a -= 1
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        a -= 1
        b -= 1
        return self.find(a) == self.find(b)

    def union(self, a, b):
        a -= 1
        b -= 1
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        a -= 1
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
        uf.find(a)
        uf.find(b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        if uf.connected(a, b):
            blockships[a].add(b)
            blockships[b].add(a)

    res = [0] * n
    for i in range(n):
        all_connections = uf.size(i + 1)
        existing = len(friendships[i + 1])
        blocked = len(blockships[i + 1])
        res[i] = all_connections - 1 - existing - blocked

    print(" ".join([str(u) for u in res]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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)]
con = [1 for _ in range(n+1)]
uni = np.array([-1 for i in range(n+1)])

def root(num, pea, index=True):
    get_index = []
    while pea[num] > 0:
        get_index.append(num)
        num = pea[num]
    if index:
        return num, get_index
    else:
        return num

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a, get_a_index = root(a, uni)
        root_b, get_b_index = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[get_a_index+get_b_index+[root_b]] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni, index=False) == root(d, uni, index=False):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni, index=False)
    result.append(-uni[root_i]-con[i])
print(*result)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = {n: None for n in nodes}
        self.sizes = {n: 1 for n in nodes}

    def find(self, a):
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
        uf.find(a)
        uf.find(b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        if uf.connected(a, b):
            blockships[a].add(b)
            blockships[b].add(a)

    res = [0] * n
    for i in range(n):
        all_connections = uf.size(i + 1)
        existing = len(friendships[i + 1])
        blocked = len(blockships[i + 1])
        res[i] = all_connections - 1 - existing - blocked

    print(" ".join([str(u) for u in res]))

Submission status: Time Limit Exceeded

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)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    while pea[num] > 0:
        num = pea[num]
    return num

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    result.append(-uni[root(i, uni)]-con[i])
print(*result)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = {n: None for n in nodes}
        self.sizes = {n: 1 for n in nodes}

    def find(self, a):
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
        uf.find(a)
        uf.find(b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        blockships[a].add(b)
        blockships[b].add(a)

    res = [0] * n
    for i in range(n):
        all_connections = uf.size(i + 1)
        existing = len(friendships[i + 1])
        blocked = sum([1 for j in blockships[i + 1] if uf.connected(i + 1, j)])
        res[i] = all_connections - 1 - existing - blocked

    print(" ".join([str(u) for u in res]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = {n: None for n in nodes}
        self.sizes = {n: 1 for n in nodes}

    def find(self, a):
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        blockships[a].add(b)
        blockships[b].add(a)

    res = [0] * n
    for i in range(n):
        all_connections = uf.size(i + 1)
        existing = len(friendships[i + 1])
        blocked = sum([1 for j in blockships[i + 1] if uf.connected(i + 1, j)])
        res[i] = all_connections - 1 - existing - blocked

    print(" ".join([str(u) for u in res]))

Submission status: Time Limit Exceeded

Solution code:
# union find (データ構造) 
# union : ある要素とある要素を集合にする：木構造とする O(logn)
# 長さが短い方をくっつける or 経路縮約
# find : ある要素がどの集合に属しているかを返す：根を調べる O(logn)

# ならし計算量：ある時点まで見た時の計算量
# アッカーマン関数の逆数

# 負でサイズ，正で親のIDを持つ
import sys
sys.setrecursionlimit(10**6)

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

    def find(self, x):
        # ある要素が度の集合に属しているかを返す
        if self.tree[x] < 0:
            # 根だったら根を返す
            return x
        else:
            # そうじゃなかったら親を返す
            return self.find(self.tree[x])

    def union(self, x, y):
        # ある要素をある要素に入れる
        x = self.find( x)
        y = self.find( y)#根同士をくっつけるかたちにする

        if x == y:
            # 処理する必要なし
            return False
        else:
            if self.tree[x] < self.tree[y]:
                # 小さい方にくっつける
                x, y = y, x
            # yをxにくっつける
            self.tree[x] += self.tree[y] # サイズ
            self.tree[y] = x # 根
            return True

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

N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = [0]*N
block = [0]*N

for _ in range(M):
    A, B = map(int, input().split())
    friend[A - 1] += 1
    friend[B - 1] += 1
    uf.union(A - 1, B - 1)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.find(C - 1) == uf.find(D - 1):
        block[C - 1] += 1
        block[D - 1] += 1

[print(max(0, uf.size(i) - friend[i] - block[i] - 1)) for i in range(N)]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
q = deque([])

def bfs(i):
    t = []
    q.append(i)
    c = [0] * n
    u = q.popleft()
    if G[u] != 0:
        for j in G[u]:
            if not c[j] != 0:
                q.append(j)
    c[u] = 1
    while len(q) != 0:
        u = q.popleft()
        c[u] = 1   
        if G[u] != 0:
            for j in G[u]:
                if c[j] == 0 and not i in G[j] and not j in t:
                    q.append(j)
                    t.append(j)
                elif c[j] == 0 and not j in t:    
                    q.append(j)   
    s = 0
    if not H[i] == 0:
        for j in t:
            if j in H[i]:
                s += 1                    
    return len(t) - s   

n, m, k = map(int, input().split())
G = [0] * n
H = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    if G[a - 1] == 0:
        G[a - 1] = [b - 1]
    else:
        G[a - 1].append(b - 1)
    if G[b - 1] == 0:
        G[b - 1] = [a - 1]
    else:
        G[b - 1].append(a - 1)
for _ in range(k):
    a, b = map(int, input().split())
    if H[a - 1] == 0:
        H[a - 1] = [b - 1]
    else:
        H[a - 1].append(b - 1)
    if H[b - 1] == 0:
        H[b - 1] = [a - 1]
    else:
        H[b - 1].append(a - 1)
for i in range(n - 1):
    print(bfs(i), end = " ")
print(bfs(n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')

Submission status: Time Limit Exceeded

Solution code:
n, m, k = list(map(int, input().split()))
link = {i: (set(), set()) for i in range(1, n+1)}

friends = 0
blocked = 1

groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a][friends].add(b)
    link[b][friends].add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c][blocked].add(d)
    link[d][blocked].add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i][blocked] - link[i][friends]) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

sys.setrecursionlimit(1000000)
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block =  collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)


def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = [0]*N
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans[i] = len(visit) - len(bl) - len(graph[i + 1]) -1
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self, v):
        self.value = v
        self.friends = set()
        self.blocked = set()

n, m, k = list(map(int, input().split()))
link = {i: Node(i) for i in range(1, n+1)}
groups = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a].friends.add(b)
    link[b].friends.add(a)
    holders = []
    for i, g in enumerate(groups):
        if a in g or b in g:
            g.add(a)
            g.add(b)
            holders.append(i)
    if len(holders) >= 2:
        ng = set()
        for h in reversed(holders):
            ng |= groups[h]
            groups.pop(h)
        groups.append(ng)
    elif len(holders) == 0:
        groups.append(set([a,b]))

for _ in range(k):
    c, d = list(map(int, input().split()))
    link[c].blocked.add(d)
    link[d].blocked.add(c)

for i in range(1, n+1):
    for g in groups:
        if i in g:
            cnt = len(g - link[i].blocked - link[i].friends) - 1 
            break
    else:
        cnt = 0
    print(cnt, end="" if i == n else " ")

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
friends = [deque() for i in range(N)]
block = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[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)


def dfs(x, y):
    for i in friends[y]:
        if check[i] == None:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = x
            dfs(x, i)
ans = [0]*N
#print(prefriends)
j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        #print(prefriends[j])
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        #print(check)
    j += 1
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))
for j in range(N):
    ans[j] = (set(prefriends[check[j]]) - set(friends[j])) - (set(block[j]) | set([j]))
    #print(ans[j])
    #print()
ans = [len(ans[i]) for i in range(N)]
print(*ans)