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:
'''
Created on 2020/03/04

@author: fanta
'''
N,M,K = map(int, input().split())
friends_set = []
enemies_set = []
groups = []
menbers = set()
group_num = -1
bond = []
count = {}
results = {}

for i in range(M):
    friends_set.append(set(int(x) for x in input().split()))

for i in range(K):
    enemies_set.append(set(int(x) for x in input().split()))

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

for friend in friends_set:
    if friend.isdisjoint(menbers):
        group_num += 1
        groups.append(set())
        groups[group_num] = friend

    else:
        for v in range(group_num+1):
            if (friend.isdisjoint(groups[v]))^True:
                groups[v] = groups[v]|friend
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]]= groups[bond[1]] | groups[bond[0]]
                groups[bond[1]].clear()
                group_num = len(groups) - 1

        bond.clear()

    menbers = menbers|friend


for enemy in enemies_set:
    enemy_list = list(enemy)
    for v in range(group_num+1):
        if enemy <= groups[v]:
            count[enemy_list[0]] += 1
            count[enemy_list[1]] += 1

for friend in friends_set:
    friend_list = list(friend)
    for v in range(group_num+1):
        if friend <= groups[v]:
            count[friend_list[0]] += 1
            count[friend_list[1]] += 1



for v in range(group_num+1):
    group_len = len(groups[v])
    for i in groups[v]:
        results[i] = group_len - 1 - count[i]


for out in results.values():
    print(out,end=' ')

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/03/04

@author: fanta
'''
N,M,K = map(int, input().split())
friends = []
enemies = []
groups = []
menbers = set()
num = -1
bond = []
count = {}
results = {}

for i in range(M):
    friends.append([int(x) for x in input().split()])

for i in range(K):
    enemies.append([int(x) for x in input().split()])

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

for friend in friends:
    if (friend[0] not in menbers) and (friend[1] not in menbers):
        num += 1
        groups.append(set())
        groups[num].add(friend[0])
        groups[num].add(friend[1])

    else:
        for v in range(num+1):
            if (friend[0] in groups[v]) or (friend[1] in groups[v]):
                groups[v].add(friend[0])
                groups[v].add(friend[1])
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]]= groups[bond[1]] | groups[bond[0]]
                groups[bond[1]].clear()
                num = len(groups) - 1

        bond.clear()

    menbers.add(friend[0])
    menbers.add(friend[1])



for enemy in enemies:
    for v in range(num+1):
        if enemy[0] in groups[v] and enemy[1] in groups[v]:
            count[enemy[0]] += 1
            count[enemy[1]] += 1

for friend in friends:
    for v in range(num+1):
        if friend[0] in groups[v] and friend[1] in groups[v]:
            count[friend[0]] += 1
            count[friend[1]] += 1


for x,y in count.items():
    for v in range(num+1):
        if x in groups[v]:
            results[x] = len(groups[v]) - 1 - y


for out in results.values():
    print(out,end=' ')

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int, input().split())
friends = []
enemies = []
groups = []
menbers = set()
num = -1
bond = []
count = {}
results = {}

for i in range(M):
    friends.append([int(x) for x in input().split()])

for i in range(K):
    enemies.append([int(x) for x in input().split()])

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

for friend in friends:
    if (friend[0] not in menbers) and (friend[1] not in menbers):
        num += 1
        groups.append([])
        groups[num].append(friend[0])
        groups[num].append(friend[1])

    else:
        for v in range(num+1):
            if (friend[0] in groups[v]) or (friend[1] in groups[v]):
                groups[v].append(friend[0])
                groups[v].append(friend[1])
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]].extend(groups[bond[1]])
                groups[bond[1]].clear()
                num = len(groups) - 1

            groups[v] = list(set(groups[v]))
        bond.clear()

    menbers.add(friend[0])
    menbers.add(friend[1])



for enemy in enemies:
    for v in range(num+1):
        if enemy[0] in groups[v] and enemy[1] in groups[v]:
            count[enemy[0]] += 1
            count[enemy[1]] += 1

for friend in friends:
    for v in range(num+1):
        if friend[0] in groups[v] and friend[1] in groups[v]:
            count[friend[0]] += 1
            count[friend[1]] += 1


for x,y in count.items():
    for v in range(num+1):
        if x in groups[v]:
            results[x] = len(groups[v]) - 1 - y


for out in results.values():
    print(out,end=' ')

Submission status: Time Limit Exceeded

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

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

import sys
sys.setrecursionlimit(1500000)

from collections import defaultdict

friend_dict = [[] for i in range(n+1)]

block_dict = [[] for i in range(n+1)]

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

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

# print(friend_dict)
# print(block_dict)

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

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

memory = {}

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

Submission status: Time Limit Exceeded

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

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

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

# print(friend_dict)
# print(block_dict)

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

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

memory = {}

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

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

for j in range(k):
    kk = list(map(int,input().split()))
    block_dict[kk[0]].append(kk[1])
    block_dict[kk[1]].append(kk[0])

# print(friend_dict)
# print(block_dict)

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

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

memory = {}

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

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
l_map = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  l_map[A - 1][B - 1] = l_map[B - 1][A - 1] = 1
for i in range(K):
  A, B = map(int, input().split())
  l_map[A - 1][B - 1] = l_map[B - 1][A - 1] = -1

def BFS(a, b):
  l_q = [a]
  l_step = []
  while len(l_q) > 0:
    start = l_q.pop(0)
    for i in range(N):
      if l_map[start][i] == 1 and not i in l_step:
        if i == b:
          return 1
        l_q.append(i)
        l_step.append(i)
  return 0
cnt = [0 for i in range(N)]
for i in range(N):
  for j in range(N):
    if i != j and l_map[i][j] == 0:
	    cnt[i] += BFS(i, j)
for i in range(N):
  cnt[i] = str(cnt[i])
print(" ".join(cnt))

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

for j in range(k):
    kk = list(map(int,input().split()))
    block_dict[kk[0]].append(kk[1])
    block_dict[kk[1]].append(kk[0])

# print(friend_dict)
# print(block_dict)

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

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

memory = {}

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

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while rmn:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

for j in range(k):
    kk = list(map(int,input().split()))
    block_dict[kk[0]].append(kk[1])
    block_dict[kk[1]].append(kk[0])

# print(friend_dict)
# print(block_dict)

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

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

memory = {}

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

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        new_fl = p[r-1]['T']
        for nf in new_fl:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    for f in fl:
        if i+1 in f:
            for s in f:
                if not s in [i+1]+ dt['T'] + dt['B']:
                    ans[i] += 1

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

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

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

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

def dfs(i):
    ret = set()
    unvisited = [i]

    while len(unvisited) > 0:
        v = unvisited.pop()
        ret.add(v)
        for w in fr[v]:
            if w in ret or w in unvisited:
                continue
            unvisited.append(w)
    return ret


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

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        tmp_fl = list(set(tmp_fl + p[r-1]['T']))
        rmn = list(set(rmn + list(set(p[r-1]['T']) - set(alr))))
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            

print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs_list(start, adjacency_list):
    unvisited = [start]
    visited = []

    while len(unvisited) > 0:
        cv = unvisited.pop()
        visited.append(cv)
        for nv in adjacency_list[cv]:
            if nv in visited:
                continue
            if nv in unvisited:
                continue
            unvisited.append(nv)

    return visited


N, M, K = map(int, input().split(' '))
deg = defaultdict(list)
to = defaultdict(list)

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

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


for i in range(N):
    group = dfs_list(i, deg)
    ans = len(group) - 1 - len(deg[i])
    for u in to[i]:
        if u in group:
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

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

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')

Submission status: Time Limit Exceeded

Solution code:
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)

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

block = []
for _ in range(k):
    a,b = map(int,input().split())
    block.append({a-1,b-1})

# print(friend)
# print(block)

for f in friend:
    f = list(f)
    uf.union(f[0],f[1])

# print(uf)

import itertools

ans = [0 for i in range(n)]

for a in uf.all_group_members().values():
    for m in a:
        tmp = len(a)-1
        for n in a:
            if {m,n} in friend or {m,n} in block:
                tmp -= 1

        ans[m] = tmp

ans = [str(i) for i in ans]
print(' '.join(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
linkList = []
ans = []
visited = [0] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = [i]
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.append(j)
    linkList.append(link)

for i in range(1,N+1):
    #連結成分のサイズ
    linkSize = 0
    #「友達関係」または「ブロック関係」はマイナスする
    minus = 0
    for link in linkList:
        if not i in link:
            continue
        for j in link:
            linkSize = len(link)
            if i in f[j] or i in b[j]:
                minus += 1
    ans.append(linkSize-minus-1)
 
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [[False]*(N+1) for _ in range(N+1)]
for i in friend:
    f[i[0]][i[1]] = True
    f[i[1]][i[0]] = True

b = [[False]*(N+1) for _ in range(N+1)]
for i in block:
    b[i[0]][i[1]] = True
    b[i[1]][i[0]] = True
    
stack=deque()
linkList = []
ans = []
nonViseted = list(range(1,N+1))

for i in range(1,N+1):
    if not i in nonViseted:
        continue
    link = [i]
    nonViseted.remove(i)
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in nonViseted:
            if f[n][j]:
                stack.append(j)
                nonViseted.remove(j)
                link.append(j)
    linkList.append(link)

for i in range(1,N+1):
    #連結成分のサイズ
    linkSize = 0
    #「友達関係」または「ブロック関係」はマイナスする
    minus = 0
    for link in linkList:
        if not i in link:
            continue
        for j in link:
            linkSize = len(link)
            if f[i][j] or b[i][j]:
                minus += 1
    ans.append(linkSize-minus-1)

print(*ans)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

for j in range(k):
    kk = list(map(int,input().split()))
    block_dict[kk[0]].append(kk[1])
    block_dict[kk[1]].append(kk[0])

# print(friend_dict)
# print(block_dict)

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

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

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


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

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

    return vis_list


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

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

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

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

print(*num_friend_candidate_array)