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:
# coding: utf-8
N,M,K=map(int,input().split())
FB=[[1 for i in range(N+1)] for j in range(N+1)]

par = [i for i in range(N+1)]
rank = [0 for i in range(N+1)]
 
def find(x):
    if x==par[x]:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
 
def unite(x,y):
    rx=find(x)
    ry=find(y)

    if rx==ry:
        return
    
    
    if rank[rx]<rank[ry]:
        par[rx]=ry
    else:
        par[ry]=rx

    if rank[rx]==rank[ry]:
        rank[rx]+=1
 

def some(x,y):
    return find(x)==find(y)
 
for i in range(M):
    A,B=map(int,input().split())
    unite(A,B)
    FB[A][B]=0
    FB[B][A]=0

for i in range(K):
    C,D=map(int,input().split())
    FB[C][D]=0
    FB[D][C]=0

ans=[0 for i in range(N)]

for i in range(1,N+1):
    for j in range(1,N+1):
        if i==j:
            FB[i][j]=0
        if FB[i][j]==0:
            continue
        else:
            if not(some(i,j)):
                FB[i][j]=0
                FB[j][i]=0

for i in range(N):
    ans[i]=sum(FB[i+1])-1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(100001)
n, m, k = map(int, input().split())
ab = []
cd = []
for _ in range(m):
    ab.append(list(map(int, input().split())))
for _ in range(k):
    cd.append(list(map(int, input().split())))
friendsof = defaultdict(list)
for a, b in ab:
    friendsof[a - 1].append(b - 1)
    friendsof[b - 1].append(a - 1)
enemiesof = defaultdict(list)
for c, d in cd:
    enemiesof[c - 1].append(d - 1)
    enemiesof[d - 1].append(c - 1)
canfrinums = []
def dps(i, output):
    output.append(i)
    for fr in friendsof[i]:
        if fr not in output:
            dps(fr, output)
for i in range(n):
    canfri_i = []
    dps(i, canfri_i)
    lencan = 0
    for x in canfri_i:
        if x != i and x not in friendsof[i] and x not in enemiesof[i]:
            lencan += 1
    canfrinums.append(lencan)
print(' '.join(map(str, canfrinums)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N,M,K = map(int, input().split())
ans = [0]*N
table = [[] for i in range(N)]
visited = [0]*N
block = [[] for i in range(N)]

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



for i in range(N):
    if visited[i] == 0:
        Q = deque()
        Q.append(i)
        visited[i] = 1
        group = deque()
        group.append(i)
        while Q:
            x = Q.popleft()
            for y in table[x]:
                if visited[y] == 0:
                    Q.append(y)
                    visited[y] = 1
                    group.append(y)
        n = len(group)
        for i in range(n):
            x = group[i]
            ans[x] += n-len(table[x])-1
            for j in range(i+1,n):
                y = group[j]
                if y in block[x]:
                    ans[x] -= 1
                    ans[y] -= 1
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, K, AB, CD):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def dfs(u):
        s = [u]
        done = set(s)
        while s:
            u = s.pop()
            for v in g[u]:
                if v not in done:
                    s.append(v)
                    done.add(v)
        return done

    group = dict()
    done = set()
    parent = [-1] * (N+1)
    for i in range(1, N+1):
        if i not in done:
            j = dfs(i)
            done |= j
            for k in j:
                parent[k] = i
            group[i] = j

    direct = defaultdict(set)
    for a, b in AB:
        direct[a].add(b)
        direct[b].add(a)
    block = defaultdict(set)
    for c, d in CD:
        block[c].add(d)
        block[d].add(c)

    ans = []
    for i in range(1, N+1):
        cand = group[parent[i]] - set([i])
        cand = cand - block[i]
        cand = cand - direct[i]
        ans.append(len(cand))
    return ans

def main():
    N, M, K = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(K)]
    print(*slv(N, M, K, AB, CD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]

n, m, k = map(int, input().split())
friendUnion = UnionFind(n)
friend = [[] for i in range(n)]

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

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

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

ans = []
for i in range(n):
    tmp = 0
    for j in range(n):
        if i == j:
            continue
        if j in block[i] or j in friend[i]:
            continue

        if friendUnion.isSameGroup(i, j):
            tmp += 1
    ans.append(str(tmp))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

	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):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

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

solve = UnionFind(N)
cntF = [0] * (N)
cntB = [0] * (N)
flg = [[0] * (N) for _ in range(N)]

for _ in range(M):
	ta,tb = map(int, input().split())
	ta -= 1
	tb -= 1
	cntF[ta] += 1
	cntF[tb] += 1
	solve.Unite(ta,tb)

	flg[ta][tb] = 1
	flg[tb][ta] = 1

for _ in range(K):
	tc,td = map(int, input().split())
	tc -= 1
	td -= 1
	if solve.isSameGroup(tc,td):
		cntF[tc] += 1
		cntF[td] += 1

ans = []
for i in range(N):
	ans.append(solve.Count(i) - cntF[i] - 1)
print(*ans)

Submission status: Time Limit Exceeded

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


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, visited):

    visited.add(v)

    for n in F[v]:
        if n in visited:
            continue
        dfs(n, visited)


for i in range(N):

    C = set()
    dfs(i, C)
    C = C - {i}
    C = C - B[i]
    C = C - F[i]

    print(len(C), end='')
    if i != N - 1:
        print(' ', end='')

print('')

Submission status: Time Limit Exceeded

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

# int = int(input())
# s = input().split()
# i = list(map(int, input().split()))
# s = [input() for i in range(3)]

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

x = list(map(int, input().split()))
n = x[0]
m = x[1]
k = x[2]

uf = UnionFind(n)

frends = []
black = []
for i in range(n):
    frends.append([])
    black.append([])

a = [-1] * m
b = [-1] * m
for i in range(m):
    x = list(map(int, input().split()))
    a = x[0] - 1
    b = x[1] - 1

    frends[a].append(b)
    frends[b].append(a)

    uf.union(a, b)

c = [-1] * k
d = [-1] * k

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

    black[c].append(d)
    black[d].append(c)

ans = []
for i in range(n):
    ans.append(str(len(list(set(uf.members(i)) - set(frends[i]) - set(black[i]) - set([i])))))

print(" ".join(ans))

Submission status: Time Limit Exceeded

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

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

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

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

def dfs(graph, start):
    visited = set([start])
    stack = []
    for f in graph[start]:
        stack.append(f)
    can_reach = set()
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                can_reach.add(c)
                stack.append(c)
    return can_reach

ans = []
for i in range(1, n + 1):
    c = dfs(graph, i)
    t = c - set(graph[i]) - set(block[i])
    ans.append(len(t))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
# ブロック関係でないかつ同じグループ
class UnionFind():
    # nはノードの数
    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]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())  # N人の人, M人の友好関係, K個のブロック関係
uf = UnionFind(N)

# inはsetを使ってオーダー1
addjacent = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    addjacent[a].add(b)
    addjacent[b].add(a)
    uf.union(a, b)
blocked = defaultdict(list)
for _ in range(K):
    c, d = map(lambda x: int(x)-1, input().split())
    blocked[c].append(d)
    blocked[d].append(c)
# 隣接している人を抜けば良い？
ans = []
for i in range(N):
    candidate = uf.members(i)
    cnt = 0
    for c in blocked[i]:
        if c in candidate:
            cnt += 1
    ans.append(max(len(candidate)-cnt - len(addjacent[i]) - 1, 0))
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
relation = [[0]*(n+1) for i in range(n+1)]
rinsetu = {i:[] for i in range(1,n+1)}
for i in range(n):
	relation[i+1][i+1] = 1
for i in range(m):
    a, b = map(int, input().split())
    relation[a][b] = 1
    relation[b][a] = 1
    rinsetu[a].append(b)
    rinsetu[b].append(a)
for i in range(k):
    a, b = map(int, input().split())
    relation[a][b] = 1
    relation[b][a] = 1

def dfs(v):
    kouho.add(v)
    for nxt in rinsetu[v]:
        if nxt in kouho:
            continue
        dfs(nxt)
gkouho = set()
kouho_list = []
for i in range(1,n+1):
	kouho = set()
	s = 0
	if (i not in gkouho):
		dfs(i)
		kouho_list.append(kouho)
		for k in kouho:
			if(relation[i][k] == 0):
				s += 1
		print(s,end=' ')
	else:
		for ks in kouho_list:
			if (i in ks):
				for k in ks:
					if(relation[i][k] == 0):
						s += 1
		print(s,end=' ')
	gkouho = gkouho | kouho

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict


graph = defaultdict(set)
banned = defaultdict(set)

N, M, K = map(int, input().split())
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


res = [0] * (N + 1)
for i in range(1, N + 1):
    queue = deque([i])
    seen = {i}
    while queue:
        cur = queue.popleft()
        if i != cur and cur not in graph[i] and cur not in banned[i]:
            res[i] += 1
        for nxt in graph[cur]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
print(*res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)

n, m, k = map(int, input().split())
friend_list = [None] * (n+1)
block_list = [None] * (n+1)
for i in range(m):
    a, b = map(int, input().split())
    if(friend_list[a] == None):
        friend_list[a] = {}
    if(friend_list[b] == None):
        friend_list[b] = {}
    friend_list[a][b] = 1
    friend_list[b][a] = 1
for i in range(k):
    a, b = map(int, input().split())
    if(block_list[a] == None):
        block_list[a] = {}
    if(block_list[b] is None):
        block_list[b] = {}
    block_list[a][b] = 1
    block_list[b][a] = 1


def dfs(owner_num, check_num, now_count, checked_list):
    if(friend_list[check_num] is not None):
        for i in friend_list[check_num]:
            if(i in checked_list):
                continue
            if(i not in block_list[owner_num] and i not in friend_list[owner_num]):
                now_count[0] += 1
            checked_list[i] = 1
            dfs(owner_num, i, now_count, checked_list)
answer = []
for i in range(1, n+1):
    now_count = [0]
    checked = {i:1}
    if(friend_list[i] is None):
        friend_list[i] = {}
    if(block_list[i] is None):
        block_list[i] = {}
    for j in friend_list[i]:
        checked[j] = 1
        dfs(i, j, now_count, checked)
    answer.append(now_count[0])

print(" ".join(str(e) for e in answer))

Submission status: Time Limit Exceeded

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

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, visited):

    visited.add(v)

    for n in F[v]:
        if n in visited:
            continue
        dfs(n, visited)


for i in range(N):

    C = set()
    dfs(i, C)
    C = C - {i}
    C = C - B[i]
    C = C - F[i]

    print(len(C), end='')
    if i != N - 1:
        print(' ', end='')

print('')

Submission status: Time Limit Exceeded

Solution code:
def dfs(node,visited,friends,connected_compnts):
    cmpnt = set()
    stack = [node]
    while stack:
        curr = stack.pop()
        if curr not in visited:
            visited.add(curr)
            cmpnt.add(curr)
            for kid in friends[curr]:
                stack.append(kid)

    connected_compnts.append(cmpnt)

def solve(cmpnt,friends,blocks,ans):
    arr = list(cmpnt)
    for node in arr:
        cmpnt.remove(node)
        add = []
        for kid in friends[node]:
            if kid in cmpnt:
                add.append(kid)
                cmpnt.remove(kid)

        blocked = set()
        for block in blocks[node]:
            blocked.add(block)
            
        ans[node] = len(cmpnt.difference(blocked))
        cmpnt.add(node)
        for kid in add:
            cmpnt.add(kid)

def main():
    n,m,k = map(int,input().split())
    friends = {}
    blocks = {}

    for i in range(1,n+1):
        friends[i] = []

    for i in range(1,n+1):
        blocks[i] = []

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

    for i in range(k):
        a,b = map(int,input().split())
        blocks[a].append(b)
        blocks[b].append(a)

    connected_compnts = []

    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            dfs(i,visited,friends,connected_compnts)

    ans = [0]*(n+1)
    for cmpnt in connected_compnts:
        solve(cmpnt,friends,blocks,ans)

    for i in range(1,n+1):
        print(ans[i],end = ' ')

main()

Submission status: Time Limit Exceeded

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


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


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

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

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

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    friend[a][b] = 1
    friend[b][a] = 1

for c, d in cd:
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1

for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if same(i, j):
            if not friend[i][j]:
                if not block[i][j]:
                    ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter


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 main():
    n, m, k = list(map(int, sys.stdin.readline().strip().split()))

    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = list(map(int, sys.stdin.readline().strip().split()))
        a -= 1
        b -= 1
        friends[a].add(b)
        friends[b].add(a)

    for i in range(k):
        c, d = list(map(int, sys.stdin.readline().strip().split()))
        c -= 1
        d -= 1
        blocks[c].add(d)
        blocks[d].add(c)

    uf = UnionFind(n)

    for f_key in friends:
        for child in friends[f_key]:
            # child_cur_group = parents[child]
            uf.union(f_key, child)

    group_num_set = defaultdict(set)
    for i in range(n):
        group = uf.find(i)
        group_num_set[group].add(i)

    ans = [0] * n
    for i in range(n):
        group = uf.find(i)
        friend_cand = group_num_set[group]
        true_friend_cand = friend_cand.difference(blocks[i]).difference(friends[i])
        ans[i] = len(true_friend_cand) - 1

    return ans


result = main()
print(' '.join([str(num) for num in result]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFindWithRank(object):
    par = []
    rank = []
    cache = True
    log = []

    def __init__(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            p = self.root(self.par[x])
            self.par[x] = p
            return p

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

    def unite(self, x, y):
        ox, oy = x, y
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            x, y = y, x
            self.par[y] = x
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

uf = UnionFindWithRank(n)
bd = dict()
fd = dict()

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True
    uf.unite(a, b)
for i in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    bd[200000 * c + d] = True
    bd[200000 * d + c] = True

res = [0] * n
for i in range(n):
    for j in range(i+1, n):
        if (200000 * i + j) not in fd and (200000 * i + j) not in bd:
            if uf.same(i, j):
                res[i] += 1
                res[j] += 1
print(" ".join(list(map(str, res))))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

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

#%%
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 group_members(self):
        return [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 a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N

for group in uf.group_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c,d in CD:
    if uf.same(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)