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:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])

direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

u = UnionFind(N)
for a,b in AB:
    u.Unite(a, b)

cluster = [[] for i in range(N)]
for n in range(N):
    cluster[u.Find_Root(n)].append(n)

for i in range(N):
    cluster[i] = set(cluster[i])

for c in cluster:
    for node in c:
        relation[node] = c

for i in range(N):
    print(len(relation[i] - set(direct_friend[i]) - set(blocked[i])) - 1, end = " ")

print("")




"""
direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

def dfs(node, p, cluster):
    cluster.append(node)
    if len(direct_friend[node]) == 1:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if len(relation[i]) == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(a, end = " ")
print("")

"""

Submission status: Time Limit Exceeded

Solution code:


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

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

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)

        if self.size[xroot] < self.size[yroot]:
            # merge to yroot
            self.par[xroot] = yroot
            self.size[yroot] = self.size[xroot] + self.size[yroot]
        else:
            # merge to xroot
            self.par[yroot] = xroot
            self.size[xroot] = self.size[xroot] + self.size[yroot]

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

    def groups(self):
        group_dict = {}

        for i in range(len(self.par)):
            root = self.find(i)
            if root not in group_dict.keys():
                group_dict[root] = {i}
            else:
                group_dict[root].add(i)

        return list(group_dict.values())


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

    friend_edge = []
    for _ in range(m):
        friend_edge.append(tuple(map(int, input().split())))

    block_edge = []
    for _ in range(k):
        block_edge.append(tuple(map(int, input().split())))

    return n, friend_edge, block_edge


def submit():
    n, friend_edge, block_edge = read_input()

    # 友達関係をUF
    uf = UnionFind(n)
    for a, b in friend_edge:
        uf.unite(a - 1, b - 1)
        
    ufgroups = uf.groups()

    # blockか、friend関係にある要素を整理
    # blockかつ、おなじufに含まれるもののみをのこす　
    remove_dict = {i : 0 for i in range(n)}
    for c, d in block_edge:
        if uf.same(c - 1, d - 1):
            remove_dict[c - 1] += 1
            remove_dict[d - 1] += 1
        
    # friend関係を整理
    for a, b in friend_edge:
        remove_dict[a - 1] += 1
        remove_dict[b - 1] += 1

    # result
    result = []
    for i in range(n):
        for gr in ufgroups:
            if i in gr:
                target = gr
                break

        result.append(len(target) - remove_dict[i] - 1)

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




if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai = bi = -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [None for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f - exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:


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

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

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)

        if self.size[xroot] < self.size[yroot]:
            # merge to yroot
            self.par[xroot] = yroot
            self.size[yroot] = self.size[xroot] + self.size[yroot]
        else:
            # merge to xroot
            self.par[yroot] = xroot
            self.size[xroot] = self.size[xroot] + self.size[yroot]

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

    def groups(self):
        group_dict = {}

        for i in range(len(self.par)):
            root = self.find(i)
            if root not in group_dict.keys():
                group_dict[root] = {i}
            else:
                group_dict[root].add(i)

        return list(group_dict.values())


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

    friend_edge = []
    for _ in range(m):
        friend_edge.append(tuple(map(int, input().split())))

    block_edge = []
    for _ in range(k):
        block_edge.append(tuple(map(int, input().split())))

    return n, friend_edge, block_edge


def submit():
    n, friend_edge, block_edge = read_input()

    # 友達関係をUF
    uf = UnionFind(n)
    for a, b in friend_edge:
        uf.unite(a - 1, b - 1)
        
    ufgroups = uf.groups()

    # blockか、friend関係にある要素を整理
    # blockかつ、おなじufに含まれるもののみをのこす　
    remove_dict = {i : set() for i in range(n)}
    for c, d in block_edge:
        if uf.same(c - 1, d - 1):
            remove_dict[c - 1].add(d - 1)
            remove_dict[d - 1].add(c - 1)
        
    # friend関係を整理
    for a, b in friend_edge:
        remove_dict[a - 1].add(b - 1)
        remove_dict[b - 1].add(a - 1)

    # result
    result = []
    for i in range(n):
        for gr in ufgroups:
            if i in gr:
                target = gr
                break

        result.append(len(target) - len(remove_dict[i]) - 1)

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




if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai = bi = -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [[] for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f - exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai, bi = -1 , -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [[] for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f - exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
# print(exclude)
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai, bi = -1 , -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [[] for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f - exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
from copy import deepcopy
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    sn = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        seen = deepcopy(sn)
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r
            
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        seen = [None]*n
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def block_check(bgraph, rks, r):
    n = len(bgraph)
    cnt = 0
    for i in range(n):
        if rks[bgraph[i]-1] == r:
            cnt += 1
    return cnt


def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(1000000)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        seen = [None]*n
        if rks[i] is None:
            c += 1
        dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def block_check(bgraph, rks, r):
    n = len(bgraph)
    cnt = 0
    for i in range(n):
        if rks[bgraph[i]-1] == r:
            cnt += 1
    return cnt


def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(1000000)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        seen = [None]*n
        if rks[i] is None:
            c += 1
        dfs(fgraph, i, c)
    
    # print(rks)
    # print(fgraph)
    # print(bgraph)
    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # block_check(bgraph[i], rks, rks[i]) 連結成分内の友達の数
        print(counter[rks[i]] - len(fgraph[i]) - block_check(bgraph[i], rks, rks[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

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

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

    def is_root(self, x):
        return self.parent[x] < 0

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


def check(i, j):
    global friends
    global blocks
    a = bisect_left(friends, [i, j])
    b = bisect_left(friends, [j, i])
    c = bisect_left(blocks, [i, j])
    d = bisect_left(blocks, [j, i])



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

friends = []
blocks = []
friend_num = [0] * n
block_num = [0] * n
uf = UnionFind(n)

for _ in range(m):
    array = list(map(int, input().split()))
    uf.unite(array[0]-1, array[1]-1)
    friends.append([array[0]-1, array[1]-1])
    friend_num[array[0]-1] += 1
    friend_num[array[1]-1] += 1

for _ in range(k):
    array = list(map(int, input().split()))
    blocks.append([array[0]-1, array[1]-1])
    block_num[array[0]-1] += 1
    block_num[array[1]-1] += 1

for i in range(n):
    uf.find(i)

for i in range(n):
    num = uf.size(i)
    personal_block_list = uf.members(i)
    personal_block_num = 0
    for j in personal_block_list:
        if [i, j] in blocks or [j, i] in blocks:
            personal_block_num += 1

    print(num-friend_num[i]-personal_block_num-1, end=' ')

Submission status: Time Limit Exceeded

Solution code:
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):

        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
            self.size[xr] += self.size[yr]
            self.size[yr] = self.size[xr]
        else:
            self.par[yr] = xr
            self.size[yr] += self.size[xr]
            self.size[xr] = self.size[yr]
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def mass_size(self):
        return [i == v for i, v in enumerate(self.par)].count(True) - 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

def main():
    from collections import defaultdict

    dicf = defaultdict(lambda :[])
    dicb = defaultdict(lambda :[])

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

    uf = union_find(N)
    for i in range(M):
        a, b = map(int, input().split())
        dicf[a].append(b)
        dicf[b].append(a)
        if a > b:
            a, b = b, a
        uf.union(a, b)

    for i in range(K):
        c, d = map(int, input().split())
        dicb[c].append(d)
        dicb[d].append(c)

    ans = []
    for i in range(1, N + 1):
        x = uf.size[uf.find(i)] - len(dicf[i]) - 1
        m = 0
        for b in dicb[i]:
            if uf.find(b) == uf.find(i):
                m += 1

        ans.append(x - m)


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




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def union(x,y):
    x = find(x)
    y = find(y)
    parent[x] = y

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x]= find(parent[x])
        return parent[x]



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)

Submission status: Time Limit Exceeded

Solution code:
# input
N, M, K = map(int, input().split())

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

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        flg = False
        for g in fg:
            if i in g and f in g:
                flg = True
                continue
            elif not (i in g or f in g):
                continue
            else:
                if i in g:
                    g.add(f)
                else:
                    g.add(i)
                
                flg = True
                break
            
        if not flg:
            fg.append(set([i, f]))

for i in range(len(fg)-1):
    for j in range(i+1, len(fg)):
        if fg[i] & fg[j] != set():
            fg[i] = fg[i] | fg[j]
            fg[j].clear()

#print(fg)

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = list(range(n))
linked = [0]*n
for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = a-1,b-1
    linked[c] += 1 
    linked[d] += 1
    while c != roots[c]:
        c = roots[c]
    while d != roots[d]:
        d = roots[d]
    if c!= d:
        roots[c] = d

for i in range(n):
    cursor = i
    while cursor != roots[cursor]:
       cursor = roots[cursor]
    roots[i] = cursor

#print(roots)
res = [0]*n
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    # same group blacklist
    if roots[c] == roots[d]:
        res[c] -= 1
        res[d] -= 1 
set_sizes = dict()

rs = list(set(roots))
for r in rs:
    count = 0
    for one in roots:
        if one == r:
            count += 1
    set_sizes[r] = count

for i in range(n):
    r = roots[i]
    res[i] += (set_sizes[r]-1-linked[i])
print (" ".join(map(str, res)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [None]*n
    sys.setrecursionlimit(1000000)
    def dfs(graph,s):
        seen[s] = s+1
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)
    rk = [list()]*n
    for i in range(n):
        seen = [None]*n
        dfs(fgraph, i)
        rk[i] = seen
    
    # print(rk)
    # print(fgraph)
    for i in range(n):
        non = {None}
        me = {i+1}
        srk = set(rk[i])-non
        bg = set(bgraph[i])
        fg = set(fgraph[i])

        print(len(srk-bg-fg-me))
        
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = list(range(n))
linked = [0]*n
for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = min(a,b)-1, max(a,b) - 1
    linked[c] += 1 
    linked[d] += 1
    while c != roots[c]:
        c = roots[c]
    while d != roots[d]:
        d = roots[d]
    e,f = min(c,d), max(c,d)
    roots[f] = e


for i in range(n):
    cursor = i
    while cursor != roots[cursor]:
       cursor = roots[cursor]
    roots[i] = cursor

#print(roots)
res = [0]*n
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    # same group blacklist
    if roots[c] == roots[d]:
        res[c] -= 1
        res[d] -= 1 
set_sizes = dict()

rs = list(set(roots))
for r in rs:
    count = 0
    for one in roots:
        if one == r:
            count += 1
    set_sizes[r] = count

for i in range(n):
    r = roots[i]
    res[i] += (set_sizes[r]-1-linked[i])
print (" ".join(map(str, res)))