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:
from collections import defaultdict
"""
unioufind
集合の中で、直接の友達 と直接のブロックを引く
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)





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

tomodachi = defaultdict(int)
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tomodachi[a] += 1
    tomodachi[b] += 1
    if not uf.judge(a,b):
        uf.union(a,b)
tomo_size = defaultdict(int)
for i in range(N):
    tomo_size[uf.find(i)] += 1


block = defaultdict(int)
for i in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    # 友達グループじゃないと無意味
    if not uf.judge(c,d):continue
    block[c] += 1
    block[d] += 1

ans = []
for i in range(N):
    a = tomo_size[uf.find(i)] - tomodachi[i] - block[i] -1 
    ans.append(a)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

class UF(object):
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = y = self.find(self.par[x])
            return y

    # x と y の集合を結合する
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            rx = self.rank[x]
            ry = self.rank[y] 
            if rx < ry:
                px, py = py, px
            elif rx == ry:
                rx += 1
            self.par[py] = px
            self.size[px] += self.size[py]
            return

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

    # x が属する集合の要素数を返す
    def get_size(self,x):
        return self.size[self.find(x)]

N,M,K = LI()
A,B = LIR(M,2)
C,D = LIR(K,2)
 
b = defaultdict(set)
t = defaultdict(set)
 
uf = UF(N)
 
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    t[A[i]-1].add(B[i]-1)
    t[B[i]-1].add(A[i]-1)
    
num = [0]*N
for i in range(K):
    if uf.is_same(C[i]-1, D[i]-1):
        num[C[i]-1] -= 1
        num[D[i]-1] -= 1
        
ans = []
for i in range(N):
    ans.append(uf.get_size(i)-1-len(t[i])+num[i])
print(*ans)

Submission status: Time Limit Exceeded

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

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

ans = [0] * n #answer
seen = [0] * n #未探索なら0、探索済なら1
todo = [] #探索保留

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] #連結要素
        seen[i] = 1
        todo.append(i)
        element.append(i)
        size = 0

        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    size += 1
                    break
            else:
                del todo[-1]

        for j in element:
            bl = 0
            for k in block[j]:
                if k in element:
                    bl += 1

            #size = len(element) - 1
            ans[j] = size - len(friend[j]) - bl
        
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

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

size = [0] * n
seen = [0] * n #未探索なら0、探索済なら1
todo = [] #探索保留

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] #連結要素
        seen[i] = 1
        todo.append(i)
        element.append(i)
        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    break
            else:
                del todo[-1]
        length = len(element)
        for j in element:
            block[j] = [k for k in block[j] if k in element]
            size[j] = length - len(friend[j]) - len(block[j]) - 1
        
    print(size[i])

Submission status: Time Limit Exceeded

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

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

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

        def unite(self,x,y):
            x = self.root(x)
            y = self.root(y)
            if x!=y:
                if self.rank[x] < self.rank[y]:
                     x,y = y,x
                if self.rank[x] < self.rank[y]:
                    self.rank[x]+=1
                self.par[y] = x
                self.size[x] +=self.size[y]
        def get_size(self,x):
            x = self.root(x)
            return self.size[x]

    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = unionfind(n)
    fr = [0 for i in range(n)]


    for i in range(m):
        a,b = map(int,input().split())
        uff.unite(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1


    ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]

    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

        def unite(self,x,y):
            x = self.root(x)
            y = self.root(y)
            if x!=y:
                self.par[y] = x
                self.size[x] +=self.size[y]
        def get_size(self,x):
            x = self.root(x)
            return self.size[x]

    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = unionfind(n)
    fr = [0 for i in range(n)]


    for i in range(m):
        a,b = map(lambda x:int(x)-1,input().split())
        uff.unite(a,b)
        fr[a]+=1
        fr[b]+=1


    ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]

    for i in range(k):
        c,d = map(lambda x:int(x)-1,input().split())
        if uff.same(c,d):
            ans[c] -=1
            ans[d] -=1
    print(*ans)
if __name__=="__main__":
    main()

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 i in range(n)]

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x!=y:
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,m,k = map(int,input().split())
uff = unionfind(n)
fr = [0 for i in range(n)]


for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    uff.unite(a,b)
    fr[a]+=1
    fr[b]+=1


ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]

for i in range(k):
    c,d = map(lambda x:int(x)-1,input().split())
    if uff.same(c,d):
        ans[c] -=1
        ans[d] -=1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m,k = map(int, input().split())
    
    def find(par, x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par, par[x])
            return par[x]
    
    def unite(par, x,y):
        x = find(par,x)
        y = find(par,y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(par, x,y):
        return find(par, x) == find(par, y)
    
    def size(par, x):
        return -par[find(par, x)]

    def members(par, x, n):
        root = find(par, x)
        return [i for i in range(n) if find(par, i) == root]
    
    friend = [-1]*n
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        unite(friend, a-1, b-1)

    block = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(k):
        a,b = map(int, input().split())
        block[a-1].append(b-1)
        block[b-1].append(a-1)

    res = []
    for i in range(n):
        x = set(members(friend, i, n))
        x = x - {i} - set(adj[i]) - set(block[i])
        res.append(len(x))
        #res.append(size(friend, i)-1-len(adj[i])-len(block[i]))
    print(*res)
    # block = [-1]*n

    # for _ in range(k):
    #     a,b = map(int, input().split())
    #     unite(block, a-1, b-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections


def dfs(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        v = stack.pop()
        if v not in visited:
            stack.extend(graph[v])
            visited.add(v)
            yield v

def read_graph(nodes, edges):
    graph = [set() for _ in range(nodes)]
    for _ in range(edges):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)
 
    return graph

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

friends = read_graph(N, M)
blockings = read_graph(N, K)

candidates = [None for _ in range(N)]
for i in range(N):
    if candidates[i] is not None:
        continue

    s = set()
    for j in dfs(friends, i):
        s.add(j)
        candidates[j] = s
    

print(
    " ".join(
        str(len(candidates[i] - friends[i] - blockings[i]) - 1) for i in range(N)
    )
)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(G, start):
    label[start] = start
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        label[target] = start
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    # visited = [k for k, x in enumerate(visited) if x ]
    # return set(visited)

N, M, K = map(int, input().split())
F_G = [[] for _ in range(N)]
B_G = [[] for _ in range(N)]
label = [-1] * N
link = [0] * N
# 無向グラフの作成
for _ in range(M):
    a, b = map(int, input().split())
    link[a-1] += 1
    link[b-1] += 1
    F_G[a-1].append(b-1)
    F_G[b-1].append(a-1)

sub = list(range(N))
# bfsでラベル付けすることで連結成分を作成
for i in sub:
    if label[i] == -1:
        bfs(F_G, i)

for _ in range(K):
    c, d = map(int, input().split())
    if label[c-1] == label[d-1]:
        link[c-1] -= 1
        link[d-1] -= 1
    B_G[c-1].append(d-1)
    B_G[d-1].append(c-1)

for i in range(len(link)):
    link[i] -= len(F_G[i])
    num = len([x for x in label if x == label[i]])
    link[i] += (num-len(F_G[i]))-1
print(*link)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(G, start):
    label[start] = start
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        label[target] = start
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    visited = [k for k, x in enumerate(visited) if x ]
    return set(visited)

N, M, K = map(int, input().split())
F_G = [[] for _ in range(N)]
B_G = [[] for _ in range(N)]
label = [-1] * N
# 無向グラフの作成
for _ in range(M):
    a, b = map(int, input().split())
    F_G[a-1].append(b-1)
    F_G[b-1].append(a-1)
for _ in range(K):
    c, d = map(int, input().split())
    B_G[c-1].append(d-1)
    B_G[d-1].append(c-1)

sub = list(range(N))
# bfsでラベル付けすることで連結成分を作成
for i in sub:
    if label[i] == -1:
        bfs(F_G, i)
for i in sub:
    linked_node = [j for j, x in enumerate(label) if x == label[i]]
    linked_num = len(linked_node)
    next_to_num = len(F_G[i])
    block_num = len([k for k in linked_node if k in B_G[i]])
    if i != N-1:
        print(linked_num - next_to_num - block_num - 1, end=" ")
    else:
        print(linked_num - next_to_num - block_num - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(G, start):
    label[start] = start
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        label[target] = start
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    visited = [k for k, x in enumerate(visited) if x ]
    return set(visited)

N, M, K = map(int, input().split())
F_G = [[] for _ in range(N)]
B_G = [[] for _ in range(N)]
label = [-1] * N
# 無向グラフの作成
for _ in range(M):
    a, b = map(int, input().split())
    F_G[a-1].append(b-1)
    F_G[b-1].append(a-1)
for _ in range(K):
    c, d = map(int, input().split())
    B_G[c-1].append(d-1)
    B_G[d-1].append(c-1)

sub = list(range(N))
for i in sub:
    can = list(range(N))
    can.pop(i) # 自分自身を友達候補から削除
    can = set(can)
    can -= set(B_G[i])     # ブロック関係にある人を友達候補から削除
    can -= set(F_G[i])     # 友達関係に既にある人を友達候補から削除
    if label[i] != -1:
        v = [l for l, x in enumerate(label) if x == label[i]]
        v = set(v)
    else:
        v = bfs(F_G, i)    # 友達グラフ上でつながっている友達をsetで取得
    can &= v               # 今の候補と積集合とって完成
    if i != N-1:
        print(len(can), end=" ")
    else:
        print(len(can))

Submission status: Time Limit Exceeded

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

class UnionFind(object):
    def __init__(self, n: int):
        """ ノードのつながりを辞書型で表現する
        要素数nであり、要素は0からn-1である想定
        >> - usage
        g = Graph(n=n)

        """
        self.adjacency_dict = {}
        self.parent = [None] * n

        for i in range(n):
            self.add_vertex(i)
            self.parent[i] = i
        self.rank = [0] * n

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def unite(self, v1: int, v2: int):
        """ ノード同士をつなぐ。"""
        if v1 == v2:
            return

        # すでにつながっている場合は親の更新のみしておく
        if self.same(v1, v2):
            return

        p1 = self.parent[v1]
        p2 = self.parent[v2]

        # つながっていない場合は親同士をつなげる
        # その場合rankが小さい方から大きい方につなげる
        if self.rank[p1] == self.rank[p2]:
            self.update(p1, p2)
            self.rank[p2] += 1
        elif self.rank[p1] < self.rank[p2]:
            self.update(p1, p2)
        else:
            self.update(p2, p1)

    def update(self, v, parent):
        self.adjacency_dict[v].append(parent)

    def same(self, v1, v2):
        """ 親が同一であれば連結 """
        self.parent[v1] = self.root(v1)
        self.parent[v2] = self.root(v2)

        return self.parent[v1] == self.parent[v2]

    def root(self, v1):
        """ vから上向きに辿って根を調べる """
        if self.adjacency_dict[v1] == []:
            return v1

        for v in self.adjacency_dict[v1]:
            parent = self.root(v)
        return parent

    def print_graph(self):
        print(self.adjacency_dict)



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


class UnionFindFriend(UnionFind):
    def __init__(self, n):
        super(UnionFindFriend, self).__init__(n)
        self.friends = {}
        self.blocks = {}

        for i in range(n):
            self.friends[i] = []
            self.blocks[i] = []

    def add_friends(self, v1, v2):
        self.friends[v1].append(v2)
        self.friends[v2].append(v1)

    def add_blocks(self, v1, v2):
        self.blocks[v1].append(v2)
        self.blocks[v2].append(v1)


def get_next():
    c1, c2 = map(int, input().split())
    c1, c2 = c1 - 1, c2 -1
    return c1, c2


uf = UnionFindFriend(N)

for i in range(M):
    c1, c2 = get_next()
    uf.unite(c1, c2)
    uf.add_friends(c1, c2)

for i in range(K):
    c1, c2 = get_next()
    uf.add_blocks(c1, c2)

# 全ての要素のroot（つまり自分がどのグループに所属するか）を格納
roots = [uf.root(i) for i in range(N)]
res = {}

# rootsからグループのリストを取得し、一つずつ処理する
for root in list(set(roots)):
    idxes = [idx for idx, element in enumerate(roots) if element == root]
    len_idxes = len(idxes)

    for idx in idxes:
        # 友達候補 = [連携成分の数 -1] - [友達の数] - [連結成分におけるブロック数]
        result = len_idxes - 1 - len(uf.friends[idx]) - len(set(uf.blocks[idx]) & set(idxes))
        res[idx] = result

for i in range(N):
    print(res[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(G, start):
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    visited = [k for k, x in enumerate(visited) if x ]
    return set(visited)

def main():
    N, M, K = map(int, input().split())
    F_G = [[] for _ in range(N)]
    B_G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        F_G[a-1].append(b-1)
        F_G[b-1].append(a-1)
    for _ in range(K):
        c, d = map(int, input().split())
        B_G[c-1].append(d-1)
        B_G[d-1].append(c-1)
    sub = list(range(N))
    for i in sub:
        can = list(range(N))
        can.pop(i)         # 自分自身を友達候補から削除
        can = set(can)
        can -= set(B_G[i]) # ブロック関係にある人を友達候補から削除
        can -= set(F_G[i]) # 友達関係に既にある人を友達候補から削除
        v = bfs(F_G, i)    # 友達グラフ上でつながっている友達をsetで取得
        can &= v           # 今の候補と積集合とって完成
        if i != N-1:
            print(len(can), end=" ")
        else:
            print(len(can))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Friend Suggestion
# https://atcoder.jp/contests/abc157/tasks/abc157_d
# 連結しているうち、現在友達関係でもブロック関係でもない人数を調べる
# つまり、友達候補 = [連携成分の数] - [友達の数] - [ブロック数]

'''
4 4 1
2 1
1 3
3 2
3 4
4 1
'''

import numpy as np
N, M, K = map(int, input().split())
# -*- coding: utf-8 -*-
# Union Find


class UnionFind(object):
    def __init__(self, n: int):
        """ ノードのつながりを辞書型で表現する
        要素数nであり、要素は0からn-1である想定
        >> - usage
        g = Graph(n=n)

        """
        self.adjacency_dict = {}
        self.parent = [None] * n

        for i in range(n):
            self.add_vertex(i)
            self.parent[i] = i
        self.rank = [0] * n

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def unite(self, v1: int, v2: int):
        """ ノード同士をつなぐ。"""
        if v1 == v2:
            return

        # すでにつながっている場合は親の更新のみしておく
        if self.same(v1, v2):
            return

        p1 = self.parent[v1]
        p2 = self.parent[v2]

        # つながっていない場合は親同士をつなげる
        # その場合rankが小さい方から大きい方につなげる
        if self.rank[p1] == self.rank[p2]:
            self.update(p1, p2)
            self.rank[p2] += 1
        elif self.rank[p1] < self.rank[p2]:
            self.update(p1, p2)
        else:
            self.update(p2, p1)

    def update(self, v, parent):
        self.adjacency_dict[v].append(parent)

    def same(self, v1, v2):
        """ 親が同一であれば連結 """
        self.parent[v1] = self.root(v1)
        self.parent[v2] = self.root(v2)

        return self.parent[v1] == self.parent[v2]

    def root(self, v1):
        """ vから上向きに辿って根を調べる """
        if self.adjacency_dict[v1] == []:
            return v1

        for v in self.adjacency_dict[v1]:
            parent = self.root(v)
        return parent

    def print_graph(self):
        print(self.adjacency_dict)


class UnionFoldFriend(UnionFind):
    def __init__(self, n):
        super(UnionFoldFriend, self).__init__(n)
        self.friends = {}
        self.blocks = {}

        for i in range(n):
            self.friends[i] = []
            self.blocks[i] = []

    def add_friends(self, v1, v2):
        self.friends[v1].append(v2)
        self.friends[v2].append(v1)

    def add_blocks(self, v1, v2):
        self.blocks[v1].append(v2)
        self.blocks[v2].append(v1)


uf = UnionFoldFriend(N)
# mat_m = np.zeros((N, N))
# mat_k = np.zeros((N, N))

for i in range(M):
    c1, c2 = map(int, input().split())
    c1, c2 = c1 - 1, c2 -1

    uf.unite(c1, c2)
    uf.add_friends(c1, c2)

for i in range(K):
    c1, c2 = map(int, input().split())
    c1, c2 = c1 - 1, c2 -1

    uf.add_blocks(c1, c2)

# res = (mat_m == 0) & (mat_k == 0)
# print(res.sum(axis=0) - 1)

# uf.print_graph()
# print(uf.friends)
# print(uf.blocks)

for i in range(N):
    group = [j for j in range(N) if (j != i) and (uf.same(i, j))]
    group = [j for j in group if (j not in uf.friends[i]) and (j not in uf.blocks[i])]
    print(len(group), end=" ")

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N, M, K = map(int, input().split())
    grid = [[0] * N for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        grid[A-1][B-1] = grid[B-1][A-1] = 1
    for _ in range(K):
        A, B = map(int, input().split())
        grid[A-1][B-1] = grid[B-1][A-1] = -1

    def dfs(i, j, grid, seen=set()):
        if grid[i][j] == 1:
            return True
        for index in range(N):
            if index == i or index == j or index in seen:
                continue
            if grid[i][index] == 1:
                if dfs(index, j, grid, seen|set([i])):
                    return True
        return False

    ans = [0] * N
    for i in range(N-1):
        for j in range(i+1, N):
            if grid[i][j] == 0 and dfs(i, j, grid):
                ans[i] += 1
                ans[j] += 1
    print(' '.join([str(_) for _ in ans]))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections


def friend_candidates(i, friends, visited=None):
    visited = set([i])
    stack = list(friends[i])

    while stack:
        v = stack.pop()
        if v in visited:
            continue

        stack.extend(friends[v])
        visited.add(v)

    return visited


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

friends = collections.defaultdict(set)
for _ in range(M):
    A, B = map(int, input().split())
    friends[A].add(B)
    friends[B].add(A)

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


table = {}
for i in range(1, N + 1):
    if i in table:
        continue

    candidates = friend_candidates(i, friends)
    for j in candidates:
        table[j] = candidates

print(
    " ".join(
        str(len(table[i] - friends[i] - blockings[i]) - 1) for i in range(1, N + 1)
    )
)

Submission status: Time Limit Exceeded

Solution code:
import collections


def friend_candidates(i, friends, visited=None):
    visited = set([i])
    stack = list(friends[i])

    while stack:
        v = stack.pop()
        if v in visited:
            continue

        stack.extend(friends[v])
        visited.add(v)

    return visited


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

friends = collections.defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    friends[A].append(B)
    friends[B].append(A)

blockings = collections.defaultdict(list)
for _ in range(K):
    C, D = map(int, input().split())
    blockings[C].append(D)
    blockings[D].append(C)


table = {}
for i in range(1, N + 1):
    if i in table:
        continue

    candidates = list(friend_candidates(i, friends))
    for j in candidates:
        table[j] = candidates

print(
    " ".join(
        str(
            len(table[i])
            - len(friends[i])
            - len(set(blockings[i]).intersection(table[i]))
            - 1
        )
        for i in range(1, N + 1)
    )
)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m, k = map(int, input().split())
L = UnionFind(n)
F = [0] * n
B = [0] * n

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

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if L.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(n):
    print(L.size(i) - F[i] - B[i] - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[-1]*n
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-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):#スタートの選び方
    u=[0]*n
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        u[x]=1
        ans[i]+=1
        for j in link[x]:
            if u[j]==1:
              continue
            elif j in q:
              continue
            else:
              q.append(j)
    s.append(u)
for i in range(n):
  for j in link[i]:
    if s[i][j]==1:
      ans[i]-=1
  for k in block[i]:
    if s[i][k]==1:
      ans[k]-=1
print(*ans)