Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    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())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        maxj = len(fg)
        while j < maxj:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    maxj -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    maxj -= 1
            j += 1

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

# 友人候補を抽出
cand = []
for i in range(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)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
#print(fg)
#print(cand)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

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)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friend_numbers = []
        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(N):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

uf_tree = UnionFindTree(N)
for (a, b) in AB:
    a -= 1
    b -= 1
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friend_numbers.append(a)
    uf_tree.unite(a, b)

for (c, d) in CD:
    c -= 1
    d -= 1
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].block_numbers.append(c)

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

        if uf_tree.same(k, n):
            candidate += 1
    candidates.append(candidate)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

FRIEND = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

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

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


def make_dfs():
    visited = [0] * n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not FRIEND[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = [-1]*n

for i in range(n):
    friends = FRIEND[i]
    dfs = make_dfs()
    possibly_friends = dfs(i)
    blocks = BLOCK[i]
    blocks = [pf and b for pf, b in zip(possibly_friends, blocks)]
    ans[i] = sum(possibly_friends) - sum(friends) - sum(blocks) - 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

FRIEND = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

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

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


def make_dfs():
    visited = [0] * n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not FRIEND[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = [-1]*n

for i in range(n):
    friends = FRIEND[i]
    dfs = make_dfs()
    possibly_friends = dfs(i)
    blocks = BLOCK[i]

    for f, pf, b in zip(friends, possibly_friends, blocks):
        if pf and (not f) and (not b):
            ans[i] += 1

print(*ans)

Submission status: Time Limit Exceeded

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

FRIEND = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

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

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



def make_dfs():
    visited = [0] * n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not FRIEND[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = [-1]*n

for i in range(n):
    friends = FRIEND[i]

    dfs = make_dfs()
    possibly_friends = dfs(i)
    blocks = BLOCK[i]

    for f, pf, b in zip(friends, possibly_friends, blocks):
        if pf and (not f) and (not b):
            ans[i] += 1

print(*ans)

Submission status: Time Limit Exceeded

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

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+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if d in uf.members(c):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)

Submission status: Time Limit Exceeded

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

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+1)

not_uf = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].append(b)
  not_uf[b].append(a)
  uf.union(a, b)

ans_list = [ uf.size(i) for i in range(N+1) ]

for _ in range(K):
  c, d = map(int, input().split())
  if d in uf.members(c):
    not_uf[c].append(d)
    not_uf[d].append(c)

print(' '.join(str(s - len(t) - 1) for s, t in zip(ans_list[1:], not_uf[1:])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind():
    # nはノードの数
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    # xはノードの番号
    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、そのグラフの要素の個数を負の値で保持している
            return x
        else:
            # 再帰的に親を探しにいき、得られた値を格納する
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

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

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

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

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

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

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = defaultdict(int)
for _ in range(M):  # 友達関係の数
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)
    friends[a] += 1
    friends[b] += 1
blocked = defaultdict(list)
for _ in range(K):  # ブロック関係の人数
    c, d = map(lambda x: int(x)-1, input().split())
    blocked[c].append(d)
    blocked[d].append(c)

for i in range(N):
    # 同じグループの人数
    group_size = uf.size(i)
    # iと直接友達の人数
    i_frends = friends[i]
    # ブロック関係の人の中で、同じグループの人を数える
    cnt = 0
    for b in blocked[i]:
        if uf.same(i, b):
            cnt += 1
    print(group_size - i_frends - cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
def friend_suggetions(n, a_b, c_d):
    union_list = [i+1 for i in range(n)]
    dame = [[] for i in range(n)]
    ans = [0 for i in range(n)]
    for v in a_b:
        if not same(union_list, v[0], v[1]):
            union_list[root(union_list, v[1])-1] = root(union_list, v[0])
    for i in range(len(union_list)):
        union_list[i] = root(union_list, i+1)
    
    for a, b in a_b:
        dame[a-1].append(b)
        dame[b-1].append(a)
    for c, d in c_d:
        if union_list[c-1] == union_list[d-1]:
            dame[c-1].append(d)
            dame[d-1].append(c)

    for i, v in enumerate(union_list):
        ans[i] += union_list.count(v) - len(dame[i]) - 1

    return ans

def root(l, x):
    if l[x-1] == x:
        return x
    else:
        return root(l, l[x-1])

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

n, m, k =[int(i) for i in input().split()]
a_b = []
c_d = []
for _ in range(m):
    a_b.append([int(i) for i in input().split()])
for _ in range(k):
    c_d.append([int(i) for i in input().split()])

s = [str(i) for i in friend_suggetions(n, a_b, c_d)]
print(' '.join(s))

Submission status: Time Limit Exceeded

Solution code:
def dfs(v, indirectly_connected, matrix, n, depth):
    if 2 <= depth:
        indirectly_connected[v] = True
    for i in range(n):
        if indirectly_connected[i]:
            continue
        if matrix[v][i] or matrix[i][v]:
            dfs(i, indirectly_connected, matrix, n, (depth + 1))


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
f_mat = [[False] * n for _ in range(n)]
b_mat = [[False] * n for _ in range(n)]
ans = []

for a, b in ab:
    for i in range(n):
        for j in range(n):
            f_mat[a][b] = True
            f_mat[b][a] = True
for c, d in cd:
    for i in range(n):
        for j in range(n):
            b_mat[c][d] = True
            b_mat[d][c] = True
for i in range(n):
    indirectly_connected = [False] * n
    dfs(i, indirectly_connected, f_mat, n, 0)
    tmp = 0
    for j in range(n):
        if (i != j) and \
          ((not f_mat[i][j]) and (not f_mat[j][i])) and \
          ((not b_mat[i][j]) and (not b_mat[j][i])) and \
          indirectly_connected[j]:
            tmp += 1
    ans.append(tmp)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
def friend_suggetions(n, a_b, c_d):
    union_list = [i+1 for i in range(n)]
    dame = [[] for i in range(n)]
    ans = [0 for i in range(n)]
    for v in a_b:
        if not same(union_list, v[0], v[1]):
            union_list[root(union_list, v[1])-1] = root(union_list, v[0])
    for i in range(len(union_list)):
        union_list[i] = root(union_list, i+1)
    
    for a, b in a_b:
        dame[a-1].append(b)
        dame[b-1].append(a)
    for c, d in c_d:
        if same(union_list, c, d):
            dame[c-1].append(d)
            dame[d-1].append(c)

    for i, v in enumerate(union_list):
        ans[i] += union_list.count(v) - len(dame[i]) - 1

    return ans

def root(l, x):
    if l[x-1] == x:
        return x
    else:
        return root(l, l[x-1])

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

n, m, k =[int(i) for i in input().split()]
a_b = []
c_d = []
for _ in range(m):
    a_b.append([int(i) for i in input().split()])
for _ in range(k):
    c_d.append([int(i) for i in input().split()])

s = [str(i) for i in friend_suggetions(n, a_b, c_d)]
print(' '.join(s))

Submission status: Time Limit Exceeded

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

edges = [[] for _ in range(n)]
cd2 = [[] for _ in range(n)]
friends = []
count = [-1] * n
g_count = 0
ans = [0] * n

for a,b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

for c,d in cd:
    cd2[c-1].append(d-1)
    cd2[d-1].append(c-1)


for i in range(n):
    if count[i] == -1:
        count[i] = g_count
        g = [i]
        q = [i]
        while q:
            l = q.pop(-1)
            for f in edges[l]:
                if count[f] == -1:
                    q.append(f)
                    g.append(f)
                    count[f] = g_count

        friends.append(g)
        g_count += 1

for i in range(n):
    x = len(set(friends[count[i]]) & set(edges[i]))
    y = len(set(friends[count[i]]) & set(cd2[i]))
    z = len(set(friends[count[i]]) & set(edges[i]) & set(cd2[i]))
    ans[i] = len(friends[count[i]]) - (x + y - z) - 1

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

Submission status: Time Limit Exceeded

Solution code:
def friend_suggetions(n, a_b, c_d):
    union_list = [i+1 for i in range(n)]
    ans = [0 for i in range(n)]
    for v in a_b:
        if not same(union_list, v[0], v[1]):
            union_list[root(union_list, v[1])-1] = root(union_list, v[0])
    for i in range(len(union_list)):
        union_list[i] = root(union_list, i+1)
    
    for i, v in enumerate(union_list):
        ans[i] += union_list.count(v)
        for a, b in a_b:
            if i == a-1 or i == b-1:
                ans[i] -= 1
        for c, d in c_d:
            if (i == c-1 or i == d-1) and union_list[c-1] == union_list[d-1]:
                ans[i] -= 1
        ans[i] -= 1

    return ans

def root(l, x):
    if l[x-1] == x:
        return x
    else:
        return root(l, l[x-1])

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

n, m, k =[int(i) for i in input().split()]
a_b = []
c_d = []
for _ in range(m):
    a_b.append([int(i) for i in input().split()])
for _ in range(k):
    c_d.append([int(i) for i in input().split()])

s = [str(i) for i in friend_suggetions(n, a_b, c_d)]
print(' '.join(s))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素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が属するグループと要素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): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素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())

#print(list(uf.all_group_members().values())) #グループ一覧を表示

n,m,k=map(int,input().split())
f=[[]for i in range(n)]
b=[[]for i in range(n)]

uf=UnionFind(n)

for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)
    f[x-1].append(y-1)
    f[y-1].append(x-1)
for _ in range(k):
    x,y=map(int,input().split())
    b[x-1].append(y-1)
    b[y-1].append(x-1)
    
for i in range(n):
    member=uf.members(i)
    cnt=0
    for j in member:
        if j in f[i] or j in b[i]:
            cnt+=1
    print(len(member)-cnt-1,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
FM=[[0]*N for _ in range(N)]
BM=[[0]*N for _ in range(N)]


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

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

q=deque([])
cnt=[0]*N

for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in F[i]:
        if visited[j]==0:
            visited[j]=1
            q.append(j)
    while q:
        c=q.popleft()
        if FM[i][c]==1:
            for j in F[c]:
                if visited[j]==0:
                    visited[j]=1
                    q.append(j)
            continue
        if BM[i][c]==0:
            cnt[i]+=1
        for j in F[c]:
            if visited[j] == 0:
                visited[j]=1
                q.append(j)



for i in cnt:
    print(str(i),end=" ")

Submission status: Time Limit Exceeded

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

result = [0]*N
ls = [[True]*N for _ in range(N)]
for i in range(N):
    ls[i][i] = False

friends = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    ls[A-1][B-1] = False
    ls[B-1][A-1] = False
    friends[A-1] += [B-1]
    friends[B-1] += [A-1]

for i in range(K):
    C, D = map(int, input().split())
    ls[C-1][D-1] = False
    ls[D-1][C-1] = False

renketu = []
for i in range(N):
    flag = True
    for x in renketu:
        if i in x:
            for j in x:
                if ls[i][j] == True:
                    result[i] += 1
            flag = False
            break
    if flag:
        visit = [i]
        now = 0
        while True:
            if ls[i][visit[now]] == True:
                result[i] += 1

            for j in set(friends[visit[now]]) - set(visit):
                visit += [j]
            if len(visit) == now+1:
                break

            now += 1

        renketu += [visit]
            

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

Submission status: Time Limit Exceeded

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

lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]
ans = [[] for _ in range(N)]

for a,b in ab:
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

    
for c,d in cd:
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)


for i in range(N):
    temp = lstab[i][:]
    visited = []
    visited = [i] + lstab[i]

    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if y in visited:continue
            if not y in lstcd[i]:
                ans[i].append(y)
            temp.append(y)
            visited.append(y)
    
print(*[len(x) for x in ans])

Submission status: Time Limit Exceeded

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

result = [0]*N
ls = [[True]*N for _ in range(N)]
for i in range(N):
    ls[i][i] = False

friends = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    ls[A-1][B-1] = False
    ls[B-1][A-1] = False
    friends[A-1] += [B]
    friends[B-1] += [A]

#blocks = [[]]*N
for i in range(K):
    C, D = map(int, input().split())
    ls[C-1][D-1] = False
    ls[D-1][C-1] = False
    #blocks[A-1] += [B]
    #blocks[B-1] += [A]

for i in range(N):
    visit = [i+1]
    candi = set()
    now = 0
    while True:
        if ls[i][visit[now]-1] == True:
            result[i] += 1

        for j in set(friends[visit[now]-1]) - set(visit):
            visit += [j]
        if len(visit) == now+1:
            break

        now += 1
            

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

F=[[] for i in range(N)] #友達関係の隣接行列
B=[[] for i in range(N)] #ブロック関係の隣接行列

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

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

q=deque([])
cnt=[0]*N

for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in F[i]:
        if visited[j]==0:
            visited[j]=1
            q.append(j)
    while q:
        c=q.popleft()
        if c in F[i]: #友達候補が友達だったら友達の友達を候補としてqに加える
            for j in F[c]:
                if visited[j]==0:
                    visited[j]=1
                    q.append(j)
            continue
        if c not in B[i]: #友達候補がブロックされていなければカウントする
            cnt[i]+=1
        for j in F[c]:
            if visited[j] == 0:
                visited[j]=1
                q.append(j)



for i in cnt:
    print(str(i),end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

F=[[] for i in range(N)]
B=[[] for i in range(N)] 

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

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

q=deque([])
cnt=[0]*N

for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in F[i]:
        if visited[j]==0:
            visited[j]=1
            q.append(j)
    while q:
        c=q.popleft()
        if c in F[i]: 
            for j in F[c]:
                if visited[j]==0:
                    visited[j]=1
                    q.append(j)
            continue
        if c not in B[i]: 
            cnt[i]+=1
        for j in F[c]:
            if visited[j] == 0:
                visited[j]=1
                q.append(j)



for i in cnt:
    print(str(i),end=" ")

Submission status: Time Limit Exceeded

Solution code:
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 = [[] for _ in range(n+1)]
    friend_lst = [[] for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        if b not in friend_lst[a]:friend_lst[a].append(b)
        if a not in friend_lst[b]:friend_lst[b].append(a)
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if d not in block_lst[c]:block_lst[c].append(d)
        if c not in block_lst[d]:block_lst[d].append(c)
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        #print(i,"の最初の友達候補の数は",uf.length(i)-1)
        f_o_f = uf.length(i) - 1
        #print(i,"の友達リスト",friend_lst[i])
        f_o_f -= len(friend_lst[i])
        #print(i,"のブロックした相手は",block_lst[i])
        f_o_f -= len([b for b in block_lst[i] if uf.is_same(i,b) and b not in friend_lst[i]])
        answer.append(f_o_f)

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






if __name__ == '__main__':
    main()