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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def dfs(i,ch,fr,fri):
    for p in fri[i]:
        if ch[p]==-1:
            ch[p]+=1
            fr.union(i,p)
            dfs(p, ch, fr, fri)


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

fri=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    fri[a].append(b)
    fri[b].append(a)
block=[[]for i in range(n)]
for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block[a].append(b)
    block[b].append(a)
#必要-1

fr=UnionFind(n)
ch=[-1]*n
for i in range(n):
    if ch[i]==-1:
        ch[i]+=1
        dfs(i,ch,fr,fri)

for i in range(n):
    print(len(set(fr.members(i))-set(fri[i])-set(block[i]))-1,end=" ")

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce
sys.setrecursionlimit(1000000)


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

    ary = []
    block = []

    for _ in range(N):
        ary.append(set())
        block.append(set())

    for _ in range(M):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        ary[A].add(B)
        ary[B].add(A)

    for _ in range(K):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        block[A].add(B)
        block[B].add(A)

    def dfs(n, closed):
        closed.add(n)
        for i in ary[n]:
            if not i in closed:
                dfs(i, closed)

    ans = []
    for i in range(N):
        s = set()
        dfs(i, s)
        for j in block[i]:
            s.add(j)
        ans.append(len(s) - len(ary[i]) - len(block[i]) - 1)
        #print(s, len(ary[i]), len(block[i]))
    ans = " ".join(map(str, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))
        print('candidate_numbers: {}'.format(node.candidate_numbers))

#def find_friend(root, target):
#    queue = [root]
#    already_list = [root.val]
#    while len(queue) > 0:
#        node = queue.pop(0)
#        if target in node.friend_numbers:
#            return True
#        if target in node.candidate_numbers:
#            return True
#        
#        for friend in node.friends:
#            if friend.val not in already_list:
#                queue.append(friend)
#                already_list.append(friend.val)

def find_friend(tree_node, target, already_list):
    for friend in tree_node.friends:
        if target in friend.friend_numbers:
            return True
        if target in friend.candidate_numbers:
            return True

    flags = []
    for friend in tree_node.friends:
        if friend.val not in already_list:
            new_already_list = already_list[:]
            new_already_list.append(friend.val)
            flags.append(find_friend(friend, target, new_already_list))
    if True in flags:
        return True
    return False


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate_numbers = []

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

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        flag = False
        # nさんが既に自分を友達候補にしていればOK
        if k in tree_nodes[n].candidate_numbers:
            flag = True
        else:
            # nさんへの友達経路があるか探索
            flag = find_friend(v, n, [v.val])
        if flag:
            candidate += 1
            v.candidate_numbers.append(n)
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

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

#for k, v in tree_nodes.items():
#    display(v)

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

Submission status: Runtime Error

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


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


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

CD = [tuple(map(int, input().split())) for i in range(K)]

tableF = collections.defaultdict(set)
tableB = collections.defaultdict(set)


G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    tableF[i].add(i)

F = collections.defaultdict(set)

for i in range(N):
    F[G.root(i)].add(i)
ans = [len(F[G.root(i)]) - 1 for i in range(N)]

for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

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

print(*ans)

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce


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

    ary = []
    block = []

    for _ in range(N):
        ary.append(set())
        block.append(set())

    for _ in range(M):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        ary[A].add(B)
        ary[B].add(A)

    for _ in range(K):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        block[A].add(B)
        block[B].add(A)

    def dfs(n, closed):
        closed.add(n)
        for i in ary[n]:
            if not i in closed:
                dfs(i, closed)

    ans = []
    for i in range(N):
        s = set()
        dfs(i, s)
        ans.append(len(s - block[i]) - len(ary[i]) - 1)
        #print(s, len(ary[i]), len(block[i]))
    ans = " ".join(map(str, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))
        print('candidate_numbers: {}'.format(node.candidate_numbers))

#def find_friend(root, target):
#    queue = [root]
#    already_list = [root.val]
#    while len(queue) > 0:
#        node = queue.pop(0)
#        if target in node.friend_numbers:
#            return True
#        if target in node.candidate_numbers:
#            return True
#        
#        for friend in node.friends:
#            if friend.val not in already_list:
#                queue.append(friend)
#                already_list.append(friend.val)

def find_friend(tree_node, target):
    for friend in tree_node.friends:
        if target in friend.friend_numbers:
            return True
        if target in friend.candidate_numbers:
            return True

    flags = []
    for friend in tree_node.friends:
        flags.append(find_friend(friend, target))
    if True in flags:
        return True
    return False


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate_numbers = []

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

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        flag = False
        # nさんが既に自分を友達候補にしていればOK
        if k in tree_nodes[n].candidate_numbers:
            flag = True
        else:
            # nさんへの友達経路があるか探索
            flag = find_friend(v, n)
        if flag:
            candidate += 1
            v.candidate_numbers.append(n)
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

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

#for k, v in tree_nodes.items():
#    display(v)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    def find(self, x):
        #根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        #同じかどうかの確認
        return self.find(x) == self.find(y)
    def union(self, x, y):
        #統合する
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0

        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0

        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0

    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n+1)
ans_li = [-1 for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    ans_li[a] -= 1
    ans_li[b] -= 1
for i in range(k):
    a,b = map(int, input().split())
    if u.find(a) == u.find(b):
        ans_li[a] -= 1
        ans_li[b] -= 1
for i in range(1,n+1):
    p = u.find(i)
    ans_li[i] += len(u.group[p])
    print(ans_li[i], end = " ")

Submission status: Runtime Error

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

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

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    x[c[i][0]-1].append(c[i][1]-1)
    x[c[i][1]-1].append(c[i][0]-1)




# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(len(uf.menbers(i))-len(set(uf.members(i))&set(x[i]))-1)

print(*ans)

Submission status: Runtime Error

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

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

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    x[c[i][0]-1].append(c[i][1]-1)
    x[c[i][1]-1].append(c[i][0]-1)




# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(len(uf.menbers)-len(set(uf.members(i))&set(x[i]))-1)

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(input, output)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = [0] * n
    e = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
        d[a - 1] += 1
        d[b - 1] += 1
    for _ in range(k):
        a, b = map(int, input().split())
        if u.same(a, b):
            e[a - 1] += 1
            e[b - 1] += 1
    ans = [0] * n
    for i in range(n):
        ans[i] = u.size(i) - 1 - d[i] - e[i]
    print(*ans)


if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
#"""
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=len(tmp)

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

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
trees = []
ref = [-1]*n    ##どのネットワーク（木）に属するか
fref = [0]*n    ##何人友達がいるか
bref = [0]*n    ##何人友達候補の中にブロック関係があるか

for i in range(m):
    a,b = map(int,input().split())
    fref[a-1] += 1
    fref[b-1] += 1
    if ref[a-1]==-1:
        if ref[b-1]==-1:
            trees.append([a,b])
            ref[a-1]=len(trees)-1
            ref[b-1]=len(trees)-1
        else:
            trees[ref[b-1]].append(a)
            ref[a-1]=ref[b-1]
    elif ref[b-1]==-1:
        trees[ref[a-1]].append(b)
        ref[b-1]=ref[a-1]
    elif ref[a-1]<ref[b-1]:
        trees[ref[a-1]] += trees[ref[b-1]]
        ref = [ref[a-1] if i == ref[b-1] else i for i in ref]
    elif ref[a-1]>ref[b-1]:
        trees[ref[b-1]] += trees[ref[a-1]]
        ref = [ref[b-1] if i == ref[a-1] else i for i in ref]
    else:
        pass

for i in range(k):
    c,d = map(int,input().split())
    if d in trees[ref[c-1]]:
        bref[c-1] +=1
        bref[d-1] +=1
tref = [len(trees[ref[i]])-1 for i in range(n)]

#print(ref)
#print(trees)
#print(tref)
#print(fref)
#print(bref)

ans = [tref[i]- fref[i] - bref[i] for i in range(n)]
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import Counter

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

fn = defaultdict(lambda: 1)
CD = [0]*K

par = list(range(N))

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

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

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

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, j, i)
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        root(uft, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-block[i])-len(friend[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int,input().split())
friends = np.array([list(map(int,input().split())) for i in range(M)])
blocks = np.array([list(map(int,input().split())) for i in range(K)])
friends.sort(axis = 1)
friends -= 1#0始まり
blocks -= 1
 
# ラベリング
labels = np.zeros(N, dtype=int)
reps = []
maxlabel = 0
for i, j in friends:
    if labels[i] == 0 and labels[j] == 0:#どちらもカラ
        maxlabel += 1
        labels[i] = labels[j] = maxlabel
    elif labels[i] == 0:#iだけカラ
        labels[i] = labels[j]
    elif labels[j] == 0:#jだけカラ
        labels[j] = labels[i]
    elif labels[i] == labels[j]:#スルー
        continue
    else:#衝突
        reps += [[labels[i], labels[j]]]
 
if len(reps) > 0:
    reps = np.array(reps)
    reps.sort(axis=1)
    ireps = reps[::-1, ::-1]
    for lab1, lab2 in ireps:
        labels[labels == lab1] = lab2
 
# 集計(blocks)
blist = [[] for _ in range(N)]
for i, j in blocks:
    blist[i] += [j]
    blist[j] += [i]
 
# 集計(friends)
flist = [[] for _ in range(N)]
for i, j in friends:
    flist[i] += [j]
    flist[j] += [i]
 
# 集計(cluster)
clist = [[] for _ in range(maxlabel+1)]
for p, lab in enumerate(labels):
    clist[lab] += [p]
 
# フレンド提案
res = []
for p in range(N):
    lab = labels[p]
    kouhos = clist[lab]
    s = -1
    for kouho in kouhos:
        if kouho not in flist[p] and kouho not in blist[p]:
            s += 1
    res += [s]
 
# 出力
print(" ".join(list(map(str, res))))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
#"""
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=len(tmp)

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

Submission status: Runtime Error

Solution code:
import numpy as np
def resolve():
    N, M, K = map(int, input().split())
    fri = np.zeros((N, N), np.int64)
    for i in range(M):
        a, b = map(int, input().split())
        fri[a-1][b-1] = 1
        fri[b-1][a-1] = 1
    blo = np.zeros((N, N), np.int64)
    for i in range(K):
        c, d = map(int, input().split())
        blo[c-1][d-1] = 1
        blo[d-1][c-1] = 1

    can = np.zeros((N, N), np.int64)
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            for j, k in enumerate(fri[v]):
                if vis[j] or k == 0:
                    continue
                s.append(j)
                if fri[i][j] != 1 and blo[i][j] != 1 and can[i][j] == 0:
                    can[i][j] = 1
    ans = []
    for i in range(N):
        ans.append(can[i].sum())
    print(*ans, sep=' ')
resolve()

Submission status: Runtime Error

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

graphs = {}
for i in range(1, n+1):
    graphs[i] = []

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


not_uses = [True] * (n+1)
def get_same_nodes(in_node, gid):
    kids = graphs[in_node]
    same_nodes = []
    for kid in kids:
        if not_uses[kid] is True:
            not_uses[kid] = gid
            same_nodes.append(kid)
            cur_same_nodes = get_same_nodes(kid, gid)
            same_nodes += cur_same_nodes
        else:
            continue
    return same_nodes

def get_graph(start_node, gid):
    not_uses[start_node] = gid
    same_nodes = get_same_nodes(start_node, gid)
    same_nodes.append(start_node)

    n_same_nodes = len(same_nodes)
    cur_kouhos = {}
    for node in same_nodes:
        friends = graphs[node]
        cur_n_friend = len(friends)
        kouho = n_same_nodes - 1 - cur_n_friend
        cur_kouhos[node] = kouho

    return same_nodes, cur_kouhos

graph_i = not_uses

gid = 1
kouhos = {}
for start_node in range(1, n+1):
    if not_uses[start_node] is not True:
        continue

    same_nodes, cur_kouhos = get_graph(start_node, gid) 
    kouhos.update(cur_kouhos)

    gid += 1

#print("kouhos", kouhos)
for _ in range(k):
    c1, c2 = map(int, input().split(" "))
    g1 = graph_i[c1]
    g2 = graph_i[c2]
    if g1 != g2:
        continue

    kouhos[c1] -= 1
    kouhos[c2] -= 1

for node in range(1, n+1):
    print kouhos[node],
print