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

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

        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 members(self, x, candidate_list):
        root = self.find(x)
        return [i for i in candidate_list if self.find(i) == root]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(uf.members(i, higher_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    higher_order_friends = [[i for i in range(N + 1)] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        higher_order_friends[a].remove(b)
        higher_order_friends[b].remove(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        higher_order_friends[c].remove(d)
        higher_order_friends[d].remove(c)

    for ans in solve(uf, higher_order_friends)[1:]:
        print(ans, end=' ')

Submission status: Time Limit Exceeded

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

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

        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 members(self, x, except_list):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i not in except_list]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(uf.members(i, first_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

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

    for ans in solve(uf, first_order_friends)[1:]:
        print(ans, end=' ')

Submission status: Time Limit Exceeded

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

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

        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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

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

    for ans in solve(uf, first_order_friends)[1:]:
        print(ans, end=' ')

Submission status: Time Limit Exceeded

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

# 最初は0
# 友達は1
# ブロックは2
# 候補は3
friends_list = [[0 for i in range(N)] for i in range(N)]

def friends_count(f_list, search_flag, init_index, search_index, N):

    for i in range(N):
        if search_flag[i] == False and f_list[search_index][i] == 1:
            search_flag[i] = True
            if f_list[init_index][i] == 0:
                f_list[init_index][i] = 3
            friends_count(f_list, search_flag, init_index, i,N)


    return friends_list


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

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    friends_list[d][c] = 2
    friends_list[c][d] = 2

count_list = []
for i in range(N):
    search_flag = [False for i in range(N)]
    search_flag[i] = True
    friends_list = friends_count(friends_list, search_flag, i, i, N)
    count_list.append(friends_list[i].count(3))

print(" ".join([str(c) for c in count_list]))

Submission status: Time Limit Exceeded

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

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

        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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends, blocked_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i] - blocked_list[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

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

    for ans in solve(uf, first_order_friends, blocked_list)[1:]:
        print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n, m, k = map(int, input().split())

fgraph = [list() for _ in range(n)]  # 隣接行列のリスト版
bgraph = [list() for _ in range(n)]  # brock関係のグラフ
cgraph = [list() for _ in range(n)]  # 友達候補のグラフ
sys.setrecursionlimit(10**9)
rks = [None]*n


def dfs(graph, s, r):  # 深さ優先探索
    if rks[s] is None:
        rks[s] = r
    for j in range(len(graph[s])):
        if rks[graph[s][j] - 1] is not None:
            continue
        dfs(graph, graph[s][j]-1, r)


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

 # fgraphの連結成分を調べる
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)  # iから始めるDFS。ｃが同じなら同じ連結成分にいる

for i in range(k):
    c, d = map(int, input().split())
    if rks[c-1] == rks[d-1]:  # 同一連結成分の中でのブロック関係のみ注目
        bgraph[c-1].append(d)
        bgraph[d-1].append(c)

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

#
# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
# ]
#
# BRR = [
#     [2, 6],
#     [7, 5],
#     [3, 1],
# ]
#
# fl = [set() for i in range(N)]
# bl = [set() for i in range(N)]


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

ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

BRR = []
for i in range(K):
    BRR.append(list(map(int,input().split())))


unionFind = UnionFind(N)


fl = [set() for i in range(N)]
bl = [set() for i in range(N)]
for ar in ARR:
    fromNode = ar[0] - 1
    toNode = ar[1] - 1
    unionFind.union(fromNode,toNode)
    fl[fromNode].add(toNode)
    fl[toNode].add(fromNode)

for br in BRR:
    fromNode = br[0] - 1
    toNode = br[1] - 1
    bl[fromNode].add(toNode)
    bl[toNode].add(fromNode)



result = []
for i in range(N):
    m = bl[i]
    n = set(unionFind.members(i))
    s = len(m & n)
    size = unionFind.size(i)
    res = size - len(fl[i]) - 1 - s
    result.append(str(res))

print(" ".join(result))

Submission status: Time Limit Exceeded

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

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

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

for _ in range(K):
    c, d = map(int, input().split())
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
    if sum(visiteds) == N:break
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

Submission status: Time Limit Exceeded

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

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

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

for _ in range(K):
    c, d = map(int, input().split())
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

Submission status: Time Limit Exceeded

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

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)]
 
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)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

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)]
 
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)
 
groups = []
visiteds = [0]*N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

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)]
 
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)
 
groups = []
visiteds = [0]*N
c = 0

for i in range(N):
    if visiteds[i] == 1: continue

    temp = [i]
    visited = [i]
    visiteds[0] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

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)]
 
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)
 
groups = []
visiteds = [0]*N
c = 0

for i in range(N):
    if visiteds[i] == 1: continue

    temp = [i]
    visited = [i]
    visiteds[0] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - {j} - set(lstcd[j]) - set(lstab[j]))
 
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#あっとのTECH LOG、ここからDFS
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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


D = {}
parent = [-1] * N
visited = [False] * N
for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    stack = [root]
    while stack:
        n = stack.pop()
        visited[n] = True
        parent[n] = root

        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    group = D[parent[iam]]
    tmp_ans = len(group) - len(F[iam]) - 1
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

ARR = []
BRR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))

for i in range(K):
    BRR.append(list(map(int,input().split())))


# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
#     [2, 6],
# ]
#
# BRR = [
#     [7, 5],
#     [3, 1],
# ]

def prepare(n, arr):
    nodes = [set() for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeLabels = [0 for i in range(n)]
    for ar in arr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].add(toNode)
        nodes[toNode].add(fromNode)

    return nodes, nodeStates, nodeLabels

def prepare2(n,brr):
    nodes = [set() for i in range(n)]
    for ar in brr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].add(toNode)
        nodes[toNode].add(fromNode)

    return nodes


def calculate(n, m, k, nodes, nodeStates, nodeLabels,blockNodes):
    q = deque()

    label = 0
    labelDict = []
    while nodeStates.count(False) > 0:

        falseIndex = nodeStates.index(False)

        q.append(falseIndex)
        mmm = set()
        while len(q) > 0:
            node = q.popleft()
            if nodeStates[node] == True:
                continue
            nodeStates[node] = True
            nodeLabels[node] = label
            childNodes = nodes[node]
            mmm.add(node)
            for childNode in childNodes:
                if nodeStates[childNode] == False:
                    q.append(childNode)

        labelDict.append(mmm)
        label = label + 1

    result = []
    for i in range(n):
        l = nodeLabels[i]

        p = labelDict[l]
        pp = blockNodes[i]
        s = p & pp
        result.append(str(len(labelDict[l]) - len(nodes[i]) - 1 - len(s)))

    print(" ".join(result))


nodes, nodeStates, nodeLabels = prepare(N, ARR)
blockNodes = prepare2(N,BRR)
calculate(N, M, K, nodes, nodeStates, nodeLabels,blockNodes)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

ARR = []
BRR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))

for i in range(K):
    BRR.append(list(map(int,input().split())))

#
# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
#     [2, 6],
# ]
#
# BRR = [
#     [7, 5],
#     [3, 1],
# ]

def prepare(n, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeLabels = [0 for i in range(n)]
    for ar in arr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes, nodeStates, nodeLabels

def prepare2(n,brr):
    nodes = [set() for i in range(n)]
    for ar in brr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].add(toNode)
        nodes[toNode].add(fromNode)

    return nodes


def calculate(n, m, k, nodes, nodeStates, nodeLabels,blockNodes):
    q = deque()

    label = 0
    labelDict = []
    while nodeStates.count(False) > 0:

        falseIndex = nodeStates.index(False)

        q.append(falseIndex)
        mmm = set()
        while len(q) > 0:
            node = q.popleft()
            if nodeStates[node] == True:
                continue
            nodeStates[node] = True
            nodeLabels[node] = label
            childNodes = nodes[node]
            mmm.add(node)
            for childNode in childNodes:
                if nodeStates[childNode] == False:
                    q.append(childNode)

        labelDict.append(mmm)
        label = label + 1

    result = []
    for i in range(n):
        l = nodeLabels[i]

        p = labelDict[l]
        pp = blockNodes[i]
        s = p & pp
        result.append(str(len(labelDict[l]) - len(nodes[i]) - 1 - len(s)))

    print(" ".join(result))


nodes, nodeStates, nodeLabels = prepare(N, ARR)
blockNodes = prepare2(N,BRR)
calculate(N, M, K, nodes, nodeStates, nodeLabels,blockNodes)

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)
 
groups = []
visiteds = [0]*N
 
for i in range(N):
    if visiteds[i] == 1:continue
    
    temp = [i]
    visited = [i]
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    for j in grp:
        ans[j] = len(set(grp) - {j} - set(lstcd[j]) - set(lstab[j]))
 
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


N, M, K = map(int, input().split())
friend_tree = UnionFind(N)
like_array = [[] for _ in range(N)]
for _ in range(M):
    # 友人木を構築する
    A, B = map(int, input().split())
    like_array[B-1].append(A-1)
    like_array[A-1].append(B-1)
    if not friend_tree.ifSame(A-1, B-1):
        friend_tree.unite(A-1, B-1)

# friend_tree.printDebugInfo()

friend_groups = {}
for i in range(N):
    root = friend_tree.root(i)
    if root in friend_groups.keys():
        friend_groups[root] += 1
    else:
        friend_groups[root] = 1

# print(friend_groups)

dislike_array = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(int, input().split())
    dislike_array[C-1].append(D-1)
    dislike_array[D-1].append(C-1)

# print(dislike_array)

answer = []
for i in range(N):
    root = friend_tree.root(i)
    friends_count = friend_groups[root] - 1

    blockd_friend = 0
    for dislike_person in dislike_array[i]:
        if friend_tree.ifSame(i, dislike_person):
            blockd_friend += 1

    kai = friends_count - blockd_friend - len(like_array[i])
    answer.append(str(kai))

print(" ".join(answer))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

ARR = []
BRR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))

for i in range(K):
    BRR.append(list(map(int,input().split())))


# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
#     [2, 6],
# ]
#
# BRR = [
#     [7, 5],
#     [3, 1],
# ]

def prepare(n, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeLabels = [0 for i in range(n)]
    for ar in arr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes, nodeStates, nodeLabels

def prepare2(n,brr):
    nodes = [[] for i in range(n)]
    for ar in brr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes


def calculate(n, m, k, nodes, nodeStates, nodeLabels):
    q = deque()

    label = 0
    labelDict = {}
    while nodeStates.count(False) > 0:

        falseIndex = nodeStates.index(False)

        q.append(falseIndex)

        while len(q) > 0:
            node = q.popleft()
            if nodeStates[node] == True:
                continue
            nodeStates[node] = True
            nodeLabels[node] = label
            childNodes = nodes[node]
            if labelDict.get(label) == None:
                labelDict.__setitem__(label,1)
            else:
                labelDict.__setitem__(label,labelDict.get(label)+1)

            for childNode in childNodes:
                if nodeStates[childNode] == False:
                    q.append(childNode)
        label = label + 1


    result = []
    for i in range(n):
        l = nodeLabels[i]
        s = 0

        for blockNode in blockNodes[i]:
            if nodeLabels[blockNode] == l:
                s = s + 1
        result.append(str(labelDict[l] - len(nodes[i]) - 1 - s))

    print(" ".join(result))


nodes, nodeStates, nodeLabels = prepare(N, ARR)
blockNodes = prepare2(N,BRR)
calculate(N, M, K, nodes, nodeStates, nodeLabels)

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)

groups = []
visiteds = [0]*N

for i in range(N):
    if visiteds[i] == 1:continue
    
    temp = [i]
    visited = [i]

    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if y in visited:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)

ans = [0]*N
for grp in groups:
    for j in grp:
        ans[j] = len(set(grp) - {j} - set(lstcd[j]) - set(lstab[j]))

print(*ans)

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)

groups = []

for i in range(N):
    jdg = False
    for grp in groups:
        if i in grp:
            jdg = True
            break
    if jdg: break
    
    temp = [i]
    visited = [i]

    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if y in visited:continue
            temp.append(y)
            visited.append(y)
    groups.append(visited)

ans = [0]*N
for grp in groups:
    for j in grp:
        ans[j] = len(set(grp) - {j} - set(lstcd[j]) - set(lstab[j]))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
    else:
        l[X]=l[Y]
        if r[X]==r[Y]:
            r[Y]+=1

for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

for i in range(N+1):
    l[i]=find(i)
t=[]
for i in range(N+1):
    p=l.count(l[i])-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))