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: Runtime Error

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

fd = [list(map(int, input().split())) for i in range(m)]
bl = [list(map(int,input().split())) for i in range(k)]

import sys
sys.setrecursionlimit(1500000000)


friend_dict = {}

block_dict = {}

for mm in fd:
    # print(mm)
    friend_dict.setdefault(mm[0], []).append(mm[1])
    friend_dict.setdefault(mm[1], []).append(mm[0])

for kk in bl:
    block_dict.setdefault(kk[0], []).append(kk[1])
    block_dict.setdefault(kk[1], []).append(kk[0])

# print(friend_dict)
# print(block_dict)

visited = [] # Array to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        visited.append(node)
        # print(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

memory = {}

for k in range(1, n + 1):
    # Driver Code
    visited = []
    if k in memory:
        visited = memory[k]
    else:
        dfs(visited, friend_dict, k)
        for v in visited:
            memory[v] = visited
    res = len(visited) - 1
    res -= len(friend_dict[k])
    # print(visited)
    # print(block_dict[k])
    # print(set(visited).intersection(set(block_dict[k])))
    if k in block_dict:
        res -= len(set(visited).intersection(set(block_dict[k])))
    print(str(res), end = ' ')

Submission status: Runtime Error

Solution code:
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

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



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

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



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.length(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, M, K = map(int, input().split())
    A = [0]*M
    B = [0]*M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
    C = [0]*K
    D = [0]*K
    for i in range(K):
        C[i], D[i] = map(int, input().split())

    par = list(range(N))

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

    ans = [0]*N

    for i in range(M):
        rA = root(A[i]-1)
        rB = root(B[i]-1)
        if rA != rB:
            par[rB] = rA

    for i in range(N):
        # 間接的友達を全列挙
        indirect_friends = [j+1 for j in range(N) if root(i)==root(j)]
        # その中から自分と直接の友達とブロック関係を除去
        direct_friends = set()
        blocked = set()
        for a, b in zip(A, B):
            if a == i+1:
                direct_friends.add(b)
            if b == i+1:
                direct_friends.add(a)
        for c, d in zip(C, D):
            if c == i+1:
                blocked.add(d)
            if d == i+1:
                blocked.add(c)
        candidate_friends = [j for j in indirect_friends if j!=i+1 and (not j in direct_friends) and (not j in blocked)]
        ans[i] = len(candidate_friends)

    print(*ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = defaultdict(set)

for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  fr[a].add(b)
  fr[b].add(a)

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl[a].add(b)
  bl[b].add(a)

def dfs(i, g):
  g.add(i)
  for a in fr[i]:
    if a not in g:
      dfs(a, g)

for i in range(n):
  s = set()
  dfs(i, s)
  for j in bl[i]:
    if j in s:
      s.remove(j)
  print(len(s) - len(fr[i]) - 1, end=' ')
print()

Submission status: Runtime Error

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p,f=[-1]*-~n,[-1]*-~n
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  f[a]-=1,
  f[b]-=1,
a=[f[i]-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

Submission status: Runtime Error

Solution code:
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
f=[[]for _ in p]
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    p[x]+=p[y]
    p[y]=x
  f[a]+=b,
  f[b]+=a,
a=[~len(f[i])-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f1, f2 = np.sort(f) - 1
  Rel[f1, f2] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probTmp = np.zeros([N,N], int)
probList[np.where(Rel!=0)] = 1
probTmp[:] = probList
for i in range(100):
  Rel = np.dot(Rel, Rel_tmp)
  probList[np.where(Rel!=0)] = 1
  if(np.sum(probList-probTmp)==0):
    break
  probTmp[:] = probList
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

friend_list = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split(' '))
    a, b = a - 1, b - 1
    friend_list[a].append(b)
    friend_list[b].append(a)

block_list = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split(' '))
    c, d = c - 1, d - 1
    block_list[c].append(d)
    block_list[d].append(c)


def dfs(s, adj_list):
    cand_list = [s]
    vis_list = []

    while len(cand_list) > 0:
        vis = cand_list.pop(-1)
        vis_list.append(vis)
        pre_cand_list = adj_list[vis]
        for cand in pre_cand_list:
            if cand in vis_list:
                continue
            if cand in cand_list:
                continue
            cand_list.append(cand)

    return vis_list


num_friend_candidate_array = [0, ] * N
visited_user_list = []

for i in range(N):
    if i in visited_user_list:
        continue

    connected_components = dfs(i, friend_list)
    visited_user_list += connected_components

    for j in connected_components:
        exclude_block_user = set(connected_components) - set(block_list[j])
        friend_candidates = len(exclude_block_user) - len(friend_list[j]) - 1
        num_friend_candidate_array[j] = max(len(friend_candidates), 0)

print(*num_friend_candidate_array)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f1, f2 = np.sort(f) - 1
  Rel[f1, f2] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probTmp = probList
probList[np.where(Rel!=0)] = 1
for i in range(100):
  Rel = np.dot(Rel, Rel_tmp)
  probList[np.where(Rel!=0)] = 1
  if(np.sum(Rel)==0):
    break
  probTmp = probList
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

friend_list = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split(' '))
    a, b = a - 1, b - 1
    friend_list[a].append(b)
    friend_list[b].append(a)

block_list = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split(' '))
    c, d = c - 1, d - 1
    block_list[c].append(d)
    block_list[d].append(c)


def dfs(s, adj_list):
    cand_list = [s]
    vis_list = []

    while len(cand_list) > 0:
        vis = cand_list.pop(-1)
        vis_list.append(vis)
        pre_cand_list = adj_list[vis]
        for cand in pre_cand_list:
            if cand in vis_list:
                continue
            if cand in cand_list:
                continue
            cand_list.append(cand)

    return vis_list


num_friend_candidate_array = [0, ] * N
visited_user_list = []

for i in range(N):
    if i in visited_user_list:
        continue

    connected_components = dfs(i, friend_list)
    visited_user_list += connected_components

    for j in connected_components:
        friend_candidates = set(connected_components) - \
            set(friend_list[j]) - set(block_list[j]) - {j}
        num_friend_candidate_array[j] = max(len(friend_candidates), 0)

print(' '.join(num_friend_candidate_array.astype(str)))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f1, f2 = np.sort(f) - 1
  Rel[f1, f2] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probList[np.where(Rel!=0)] = 1
for i in range(100):
  Rel = np.dot(Rel, Rel_tmp)
  probList[np.where(Rel!=0)] = 1
  if(np.sum(Rel) < 1):
    break
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f1, f2 = np.sort(f) - 1
  Rel[f1, f2] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probList[np.where(Rel!=0)] = 1
for i in range(100):
  Rel = Rel * Rel_tmp
  probList[np.where(Rel!=0)] = 1
  if(np.sum(Rel) < 1):
    break
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0

[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f1, f2 = np.sort(f) - 1
  Rel[f1, f2] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probList[np.where(Rel!=0)] = 1
for i in range(100):
  Rel = Rel * Rel_tmp
  probList[np.where(Rel!=0)] = 1
  if(np.sum(Rel) < 1):
    break
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
import numpy as np

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

friend_graph = np.zeros((N, N), dtype=np.uint8)
for _ in range(M):
    a, b = map(int, input().split(' '))
    friend_graph[a-1, b-1] = 1
    friend_graph[b-1, a-1] = 1

block_graph = np.zeros((N, N), dtype=np.uint8)
for _ in range(K):
    c, d = map(int, input().split(' '))
    block_graph[c-1, d-1] = 1
    block_graph[d-1, c-1] = 1


def dfs(s, adj_mat):
    cand_list = [s]
    vis_list = []

    while len(cand_list) > 0:
        vis = cand_list.pop(-1)
        vis_list.append(vis)
        pre_cand_list = np.where(adj_mat[vis] == 1)[0]
        for cand in pre_cand_list:
            if cand in vis_list:
                continue
            if cand in cand_list:
                continue
            cand_list.append(cand)

    return vis_list


num_friend_candidate_array = np.zeros(N, dtype=np.uint8)
visited_user_list = []

for i in range(N):
    if i in visited_user_list:
        continue

    connected_components = dfs(i, friend_graph)
    print(i, connected_components)
    num_connected_components = len(connected_components)
    visited_user_list += connected_components

    for j in connected_components:
        block_user = np.where(block_graph[j] == 1)[0]
        exclude_block_user = [
            cc for cc in connected_components if cc not in block_user]

        ans = len(exclude_block_user) - friend_graph[j].sum() - 1
        num_friend_candidate_array[j] = max(ans, 0)

print(' '.join(num_friend_candidate_array.astype(str)))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f = np.sort(f) - 1
  Rel[f] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probList[np.where(Rel!=0)[0]] = 1
for i in range(100):
  Rel = Rel * Rel_tmp
  probList[np.where(Rel!=0)[0]] = 1
  if(np.sum(Rel) < 1):
    break
for f in F:
  f1, f2 = f - 1
  probList[f1, f2] = 0
  probList[f2, f1] = 0
for b in B:
  b1, b2 = b - 1
  probList[b1, b2] = 0
  probList[b2, b1] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = [int(i) for i in input().split()]
Rel = np.zeros([N, N], int)
F = np.array([[int(i) for i in input().split()] for _ in range(M)])
B = np.array([[int(i) for i in input().split()] for _ in range(K)])
for f in F:
  f = np.sort(f) - 1
  Rel[f] = 1
Rel += Rel.T
Rel_tmp = Rel
probList = np.zeros([N,N], int)
probList[np.where(Rel!=0)[0]] = 1
for i in range(100):
  Rel = Rel * Rel_tmp
  probList[np.where(Rel!=0)[0]] = 1
  if(np.sum(Rel) < 1):
    break
for f in F:
  f = np.sort(f) - 1
  probList[f] = 0
  probList[f[::-1]] = 0
for b in B:
  b = np.sort(b) - 1
  probList[(b)] = 0
  probList[(b)[::-1]] = 0
for i in range(N):
  probList[i][i] = 0
[print(np.sum(probList[i])) for i in range(N)]

Submission status: Runtime Error

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
cluster_label = [-1 for _ in range(N+1)]
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  cluster_label[i] = len(clusters)
  cluster_label[j] = len(clusters)
  clusters.append([i,j])
def search_cluster(i):
  return cluster_label[i]
def add_cluster(i, n):
  cluster_label[i] = n
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  for mem in clusters[m]:
    cluster_label[mem] = n
  clusters[n].extend(clusters[m])
  clusters[m] = -1
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
clusters.append([-1])
[print(len([j for j in clusters if((j not in friends[i])&(j not in blocks[i])&(j!=i))])) for j in range(1,N+1)]

Submission status: Runtime Error

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
cluster_label = [-1 for _ in range(N+1)]
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  cluster_label[i] = len(clusters)
  cluster_label[j] = len(clusters)
  clusters.append([i,j])
def search_cluster(i):
  return cluster_label[i]
def add_cluster(i, n):
  cluster_label[i] = n
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  for mem in clusters[m]:
    cluster_label[mem] = n
  clusters[n].extend(clusters[m])
  clusters.pop(m)
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
for i in range(1,N+1):
  n = search_cluster(i)
  if(n == -1):
    print(0)
  else:
    cluster = clusters[n]
    print(len([j for j in cluster if((j not in friends[i])&(j not in blocks[i])&(j!=i))]))

Submission status: Runtime Error

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  clusters.append([i,j])
def search_cluster(i):
  n = 0
  for cluster in clusters:
    if(i in cluster):
      return n
    n += 1
  return -1
def add_cluster(i, n):
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  clusters[n].extend(clusters[m])
  clusters.pop(m)
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
for i in range(1,N+1):
  cluster = clusters[search_cluster(i)]
  print(len([j for j in cluster if((j not in friends[i])&(j not in blocks[i])&(j!=i))]))

Submission status: Runtime Error

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  clusters.append([i,j])
def search_cluster(i):
  n = 0
  for cluster in clusters:
    if(i in cluster):
      return n
    n += 1
  return -1
def add_cluster(i, n):
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  clusters[n].extend(clusters[m])
  clusters.remove(m)
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
for i in range(1,N+1):
  cluster = clusters[search_cluster(i)]
  print(len([j for j in cluster if((j not in friends[i])&(j not in blocks[i])&(j!=i))]))

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
import sys
sys.setrecursionlimit(10**9)

def dfs(g, visited_li, now):
  for nxt in g[now]:
    if visited_li[nxt] == 1:
      continue
    visited_li[nxt] = 1
    visited_li = dfs(g, visited_li, nxt)
  return visited_li

def run():
  N, M, K = map(int, input().split())
  fg = {}
  bg = {}
  t_li = np.zeros((N+1, N+1), dtype=np.bool)
  #t_li2 = np.zeros(N+1, dtype=np.int16)
  for n in range(N):
    fg[n+1] = []
    bg[n+1] = []
  for m in range(M):
    A, B = map(int, input().split())
    fg[A].append(B)
    fg[B].append(A)
    t_li[A][B], t_li[B][A] = 1, 1
  for k in range(K):
    C, D = map(int, input().split())
    bg[C].append(D)
    bg[D].append(C)
    t_li[C][D], t_li[D][C] = 1, 1
  visited_li = np.zeros(N+1, dtype=np.int8)
  visited_li[0] = 1
  t = 1
  ans = 0
  while sum(visited_li) < (N+1):
    nxt = np.where(visited_li==0)[0][0]
    pre_visited_li = copy.copy(visited_li)
    visited_li = dfs(fg, visited_li, nxt)
    now_visi = visited_li-pre_visited_li
    #for n in np.where(now_visi==1)[0]:
    #  t_li2[n] = sum(t_li[n]*now_visi)
    #print(t_li)
    #print(now_visi)
    t_li2 = now_visi*(np.dot(now_visi, t_li.T))
    t = visited_li.sum() - pre_visited_li.sum() - 1
    #print(t_li2)
    ans += now_visi*(t - t_li2)
    #print(visited_li, t)
  print(' '.join(map(str, ans[1:])))
  
    
if __name__ == '__main__':
  run()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
import sys
sys.setrecursionlimit(10**9)

def dfs(g, visited_li, now):
  for nxt in g[now]:
    if visited_li[nxt] == 1:
      continue
    visited_li[nxt] = 1
    visited_li = dfs(g, visited_li, nxt)
  return visited_li

def run():
  N, M, K = map(int, input().split())
  fg = {}
  bg = {}
  t_li = np.zeros((N+1, N+1), dtype=np.int16)
  #t_li2 = np.zeros(N+1, dtype=np.int16)
  for n in range(N):
    fg[n+1] = []
    bg[n+1] = []
  for m in range(M):
    A, B = map(int, input().split())
    fg[A].append(B)
    fg[B].append(A)
    t_li[A][B], t_li[B][A] = 1, 1
  for k in range(K):
    C, D = map(int, input().split())
    bg[C].append(D)
    bg[D].append(C)
    t_li[C][D], t_li[D][C] = 1, 1
  visited_li = np.zeros(N+1, dtype=np.bool)
  visited_li[0] = 1
  t = 1
  ans = 0
  while sum(visited_li) < (N+1):
    nxt = np.where(visited_li==0)[0][0]
    pre_visited_li = copy.copy(visited_li)
    visited_li = dfs(fg, visited_li, nxt)
    now_visi = visited_li-pre_visited_li
    #for n in np.where(now_visi==1)[0]:
    #  t_li2[n] = sum(t_li[n]*now_visi)
    #print(t_li)
    #print(now_visi)
    t_li2 = now_visi*(np.dot(now_visi, t_li.T))
    t = visited_li.sum() - pre_visited_li.sum() - 1
    #print(t_li2)
    ans += now_visi*(t - t_li2)
    #print(visited_li, t)
  print(' '.join(map(str, ans[1:])))
  
    
if __name__ == '__main__':
  run()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
part_time1 = 0
part_time2 = 0
#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]
    
time_all.append(time.time()-start)

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = [False]*N
label = [0]*N
todo = deque()
num = 0
minus = [0]*N

time_all.append(time.time()-start)
 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1

time_all.append(time.time()-start)
count = 0
for k in range(N):
    time1 = time.time()
    num+=1
    if seen[k] == False:
        H = k
    else:
        continue
    todo += [(H)]
    seen[H] = True
    group = []
    part_time1 += time.time() - time1
    while not len(todo) == 0:
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            count+=1
            if seen[i] == False:
                todo += [i]
                seen[i] = True
#print(count)
time_all.append(time.time()-start)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1
    
time_all.append(time.time()-start)

for i in range(1,N+1):
    print(accompany[label[i]] + minus[i]-1)

time_all.append(time.time()-start)

#print(time_all)

Submission status: Runtime Error

Solution code:
f = open('C:/Users/naoki/Desktop/Atcoder/input.txt')

def make_list(length, loop):
    result = [[] for _ in range(length)]
    for _ in range(loop):
        a, b = map(lambda x: int(x) - 1, f.readline().split())
        result[a].append(b)
        result[b].append(a)
    return result

def main():
    # 敢えてDFSで解いてみる．
    n, m, k = map(int, f.readline().split())
    friend = make_list(n, m)
    brock = make_list(n, k)
    answer = [0] * n
    group_index = [0] * n
    group_id = 1

    def dfs(index):
        q = [index]
        group_index[index] = group_id
        connection = 1
        while not q == []:
            now = q.pop()
            for f in friend[now]:
                if group_index[f] == 0:
                    connection += 1
                    group_index[f] = group_id
                    q.append(f)
        return connection

    id_and_elements = {}
    for i in range(n):
        if group_index[i] == 0:
            id_and_elements[group_id] = dfs(i)
            group_id += 1

    for i in range(n):
        answer[i] += id_and_elements[group_index[i]] - 1
        answer[i] -= len(friend[i])
        for b in brock[i]:
            if group_index[b] == group_index[i]:
                answer[i] -= 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()