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:
# -*- 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 = []
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)]

#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 = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
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)

for k in range(N):
    if False not in seen:
        break
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = []
    for j in range(N):
        if len(todo) <= 0:
            break
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)
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


print(" ".join(map(lambda x,y : str(accompany[x]+y-1), label, minus)))
#for i in range(N):
#    print(accompany[label[i]] + minus[i]-1)
time_all.append(time.time()-start)

#print(time_all)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        
        # parents が負の時は要素数
        # parents が正の時は親の番号
        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)
 
        # 根が同じ場合はreturn
        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
 
    # xの木の要素数を求める
    def size(self,x):
        return - self.parents[self.find(x)]
 
    # xとyが同じ木なのか確かめる
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
 
n, m, k = (int(x) for x in input().split())

uf = UnionFind(n)
n_find = [0] * n

for i in range(n):
    a, b = (int(x) for x in input().split())

    a -= 1
    b -= 1

    n_find[a] += 1
    n_find[b] += 1
    uf.union(a, b)

ans = [uf.size(i) -1 - n_find[i] for i in range(n)] 

for i in range(k):
    c, d = (int(x) for x in input().split())

    c -= 1
    d -= 1

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

print(*ans)

Submission status: Runtime Error

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

@author: naoki
"""
from collections import deque

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

#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 = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
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
    
while False in seen:
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)

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

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

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
##        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
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(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 numpy as np
import copy

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.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)
    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:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [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
        self.parents[y] = x
        self.count[x] +=  self.count[y]

n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int, input().split())
A = []
for i in range(N):
    A.append([])
table = np.zeros((N,N))
Ftable = np.zeros((N,N))

if M > 0:
    for i in range(M):
        j,k = map(int, input().split())
        #Aに友達を保存
        A[j-1].append(k)
        A[k-1].append(j)
        table[j-1][k-1] = 1
        table[k-1][j-1] = 1
    
def itr(num,savenum):#num 今見ている人　savenum 数えたい人
    for i in A[num-1]:
        for j in A[i-1]:
            #num番目の人の友達の友達を順にみていく
            if table[savenum-1][j-1] != 1 and Ftable[savenum-1][j-1] != 1 and j != savenum:
                #savenumと友達でなく　まだFtableにも入れていない savenum自身でもないjがきたとき
                #jを友達候補にいれる
                Ftable[savenum-1][j-1] = 1
                itr(i,savenum)

for i in range(N):
    itr(i+1,i+1)
#print(Ftable)

#ブロックの処理
if K > 0:
    for i in range(K):
        j,k = map(int, input().split())
        if Ftable[j-1][k-1] == 1:
            Ftable[j-1][k-1] = 0
            Ftable[k-1][j-1] = 0

ans = [int(i) for i in sum(Ftable)]
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int, input().split())
A = []
for i in range(N):
    A.append([])
table = np.zeros((N,N))
Ftable = np.zeros((N,N))

for i in range(M):
    j,k = map(int, input().split())
    #Aに友達を保存
    A[j-1].append(k)
    A[k-1].append(j)
    table[j-1][k-1] = 1
    table[k-1][j-1] = 1
    
def itr(num,savenum):#num 今見ている人　savenum 数えたい人
    for i in A[num-1]:
        for j in A[i-1]:
            #num番目の人の友達の友達を順にみていく
            if table[savenum-1][j-1] != 1 and Ftable[savenum-1][j-1] != 1 and j != savenum:
                #savenumと友達でなく　まだFtableにも入れていない savenum自身でもないjがきたとき
                #jを友達候補にいれる
                Ftable[savenum-1][j-1] = 1
                itr(i,savenum)

for i in range(N):
    itr(i+1,i+1)
#print(Ftable)

#ブロックの処理
for i in range(K):
    j,k = map(int, input().split())
    if Ftable[j-1][k-1] == 1:
        Ftable[j-1][k-1] = 0
        Ftable[k-1][j-1] = 0

ans = [int(i) for i in sum(Ftable)]
print(' '.join(map(str, ans)))

Submission status: Runtime Error

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

@author: naoki
"""
from collections import deque

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

#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 = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1].append(pair[1]-1)
    connection[pair[1]-1].append(pair[0]-1)
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
    
while False in seen:
    num+=1
    H = seen.index(False)
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo.append(i)
                seen[i] = True    
    #print(group)

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

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

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [] # parent

def init():
    for i in range(N):
        par.append(i)

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

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

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[x] = y


init()

block_num = [0]*N
friend_num = [0]*N
cls_cnt = {} # cluster count

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


for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    if same(a,b):
        friend_num[a] += 1
        friend_num[b] += 1


for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    if same(c,d):
        block_num[c] += 1
        block_num[d] += 1


cls_cnt = {} # cluster count
for i in range(N):
    r = root(i)
    if r in cls_cnt:
        cls_cnt[r] += 1
    else:
        cls_cnt[r] = 1


for i in range(N):
    r = root(i)
    ans = cls_cnt[r] - 1 - friend_num[i] - block_num[i]
    print(ans , end=' ')

Submission status: Runtime Error

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

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        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 same(self, x, y):
        return self.find(x) == self.find(y)

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

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

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

uf_tree = UnionFindTree(N)
friends = {}
blocks = {}

for (a, b) in AB:
    a -= 1
    b -= 1
    if a not in friends:
        friends[a] = []
    if b not in friends:
        friends[b] = []
    friends[a].append(b)
    friends[b].append(a)
    uf_tree.unite(a, b)

candidates = []
#print(uf_tree.parent)
#print(uf_tree.rank)
#print(friends)
#print(blocks)
for n in range(N):
    same_union_list = uf_tree.same_union_list(n)
    #print('{}\'s union_list: {}'.format(n, same_union_list))
    candidates.append(len(same_union_list) - len(friends[n]))

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

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Submission status: Runtime Error

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

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        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 same(self, x, y):
        return self.find(x) == self.find(y)

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

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

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

uf_tree = UnionFindTree(N)
friends = {}
blocks = {}

for (a, b) in AB:
    a -= 1
    b -= 1
    if a not in friends:
        friends[a] = []
    if b not in friends:
        friends[b] = []
    friends[a].append(b)
    friends[b].append(a)
    uf_tree.unite(a, b)

for (c, d) in CD:
    c -= 1
    d -= 1
    if c not in blocks:
        blocks[c] = []
    if d not in blocks:
        blocks[d] = []
    blocks[c].append(d)
    blocks[d].append(c)

candidates = []
#print(uf_tree.parent)
#print(uf_tree.rank)
#print(friends)
#print(blocks)
for n in range(N):
    same_union_list = uf_tree.same_union_list(n)
    #print('{}\'s union_list: {}'.format(n, same_union_list))
    if n in blocks:
        for b in blocks[n]:
            if b in same_union_list:
                same_union_list.remove(b)
    candidates.append(len(same_union_list) - len(friends[n]))

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Submission status: Runtime Error

Solution code:
import time

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        dfs(i)
    return

for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])

time.sleep(3)

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:


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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        dfs(i)
    return

for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:


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

friends = [[] for i in range(n)]
cands = [[] for i in range(n)]
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        dfs(i)
    return

for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    for fr in cycle:
        cands[fr] = cycle
        count[fr] = l - 1 - len(friends[fr])

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cands[b]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

par=[None]*n
frmember=defaultdict(int)

def dfs(v):
    if par[i]==None:
        par[v]=v
        frmember[par[v]]+=1
    for f in friend[v]:
        if par[f]==None:
            par[f]=par[v]
            frmember[par[v]]+=1
            dfs(f)

for i in range(n):
    if par[i]==None:
        dfs(i)

ans=[0]*n
for i in range(n):
    ans[i]+=frmember[par[i]]-len(friend[i])-1

for i in range(k):
    a,b=map(int, input().split()) 
    if par[a-1]==par[b-1]:
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)
# process
# 友人グループを作成
fg = []
for i in range (1, N):
    fs = Frends[i]
    for f in fs:
        t = -1
        for j in range(len(fg)):
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j
                else:
                    fg[t] = np.union1d(fg[t], g)
                    fg.pop(j)
            elif not (i in g or f in g):
                continue
            else:
                if t < 0:
                    t = j
                    if i in g:
                        fg[j] = np.append(g, f)
                    else:
                        fg[j] = np.append(g, i)
                else:
                    fg[t] = np.union1d(fg[t], g)
                    fg.pop(j)

        if t < 0:
            fg.append(np.array([i, f]))

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

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

# output
#print(fg)
#print(cand)
print(" ".join(map(str, ans[1:])))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M,K = map(int,input().split())
fri = [[] for i in range(N+1)] #iさんの友達
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
bro = [[] for i in range(N+1)] #iさんのブロック
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

def dfs(i):
    seen[i] = True
    size_is[cur] += 1
    n_is[i] = cur
    for a in fri[i]:
        if not seen[a]: dfs(a)

seen = [False]*(N+1)
n_is = [0]*(N+1)
size_is = [0]
cur = 0
for i in range(1,N+1):
    if not seen[a]: #Falseで入る
        cur += 1
        size_is.append(0)
        dfs(i)

ans = [0]*N
for a in range(1,N+1):
    ans[a-1] = size_is[n_is[a]]-1
    for b in fri[a]:
        if n_is[b] == n_is[a]: ans[a-1] -= 1
    for d in bro[a]:
        if n_is[d] == n_is[a]: ans[a-1] -= 1

ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
fri = [[] for i in range(N+1)] #iさんの友達
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
bro = [[] for i in range(N+1)] #iさんのブロック
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

def dfs(i):
    seen[i] = True
    size_is[cur] += 1
    n_is[i] = cur
    for a in fri[i]:
        if not seen[a]: dfs(a)

seen = [False]*(N+1)
n_is = [0]*(N+1)
size_is = [0]
cur = 0
for i in range(1,N+1):
    if not seen[a]: #Falseで入る
        cur += 1
        size_is.append(0)
        dfs(i)

ans = [0]*N
for a in range(1,N+1):
    ans[a-1] = size_is[n_is[a]]-1
    for b in fri[a]:
        if n_is[b] == n_is[a]: ans[a-1] -= 1
    for d in bro[a]:
        if n_is[d] == n_is[a]: ans[a-1] -= 1

ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(999999999999)

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
        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
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(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
sys.setrecursionlimit(5000)

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
        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
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(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:
n, m, k = map(int,input().split())

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

for i in range(m):
    mm = list(map(int,input().split()))
    # print(mm)
    friend_dict[mm[0]].append(mm[1])
    friend_dict[mm[1]].append(mm[0])

for j in range(k):
    kk = list(map(int,input().split()))
    block_dict[kk[0]].append(kk[1])
    block_dict[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)


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