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:
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:
        friend_candidates = set(connected_components) - \
            set(friend_list[j]) - set(block_list[j]) - {j}
        num_friend_candidate_array[j] = max(len(friend_candidates), 0)

print(*num_friend_candidate_array)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np

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 = np.zeros(N, dtype=np.uint8)
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:
        friend_candidates = set(connected_components) - \
            set(friend_list[j]) - set(block_list[j]) - {j}
        num_friend_candidate_array[j] = max(len(friend_candidates), 0)

print(' '.join(num_friend_candidate_array.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
cluster_label = [-1 for _ in range(N+1)]
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  cluster_label[i] = len(clusters)
  cluster_label[j] = len(clusters)
  clusters.append([i,j])
def search_cluster(i):
  return cluster_label[i]
def add_cluster(i, n):
  cluster_label[i] = n
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  for mem in clusters[m]:
    cluster_label[mem] = n
  clusters[n].extend(clusters[m])
  clusters[m] = -1
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
for i in range(1,N+1):
  n = search_cluster(i)
  if(n == -1):
    print(0)
  else:
    cluster = clusters[n]
    print(len([j for j in cluster if((j not in friends[i])&(j not in blocks[i])&(j!=i))]))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  clusters.append([i,j])
def search_cluster(i):
  n = 0
  for cluster in clusters:
    if(i in cluster):
      return n
    n += 1
  return -1
def add_cluster(i, n):
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  clusters[n].extend(clusters[m])
  clusters.pop(m)
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
for i in range(1,N+1):
  n = search_cluster(i)
  if(n == -1):
    print(0)
  else:
    cluster = clusters[n]
    print(len([j for j in cluster if((j not in friends[i])&(j not in blocks[i])&(j!=i))]))

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


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([])
G=[]
visited=[0]*N
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                q.append([j,c])
    G.append(c)

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  b in g:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),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)]


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([])
G=[]
visited=[0]*N
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                q.append([j,c])
    G.append(c)

ans=[0]*N

for g in G:
    for i in g:
        cnt=0
        for j in B[i]:
            if j in g:
                cnt+=1
        ans[i]=len(g)-len(F[i])-cnt-1

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m,k = map(int,input().split())
ab = [[] for _ in range(n)]
for _ in range(m):
    a, b= (int(x) for x in input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
bl = [[] for _ in range(n)]
for _ in range(k):
    a, b= (int(x) for x in input().split())
    bl[a-1].append(b-1)
    bl[b-1].append(a-1)
ans = []
#print(ab)
#print(bl)
check = [0]*n
for i in range(n):
    check = [0]*n
    first = copy.copy(ab[i])
    #print(ab)
    #print(first)
    move = []
    check[i] = 1
    while len(first)>0:
        p = first.pop(0)
        check[p] = 1
        for q in ab[p]:
            #print(q)
            move.append(q)
    #print(move)
    count = 0
    while len(move):
        j = move.pop(0)
        if check[j] == 0 :
            check[j] = 1
            if j not in bl[i]:
                count += 1
            for k in ab[j]:
                move.append(k)
    ans.append(count)
#print(ans)
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

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

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
#seen = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
time_all.append(time.time()-start)

for k in range(N):
    if False not in seen:
        break
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = []
    for j in range(N):
        if len(todo) <= 0:
            break
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)
time_all.append(time.time()-start)
for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1


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

#print(time_all)

Submission status: Time Limit Exceeded

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

@author: naoki
"""
from collections import deque

#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
#seen = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
    
for k in range(N):
    if False not in seen:
        break
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = []
    for j in range(N):
        if len(todo) <= 0:
            break
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1

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

Submission status: Time Limit Exceeded

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

@author: naoki
"""
from collections import deque

#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = {i:False for i in range(N)}
#seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
    
while False in seen.values():
    num+=1
    #H = seen.index(False)
    H = [k for k,v in seen.items() if v == False][0]
    todo += [(H)]
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1

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

Submission status: Time Limit Exceeded

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

@author: naoki
"""
from collections import deque

#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
#seen = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
    
while False in seen:
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1

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

Submission status: 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])

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

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,m,k = map(int,input().split())
uf = UnionFind(n)
block = {i:[] for i in range(n)}
count = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)   
    block[min(a-1,b-1)].append(max(a-1,b-1))
for i in range(k):
    c,d = map(int,input().split())
    block[min(c-1,d-1)].append(max(c-1,d-1))
for j in uf.all_group_members():
    for k in uf.all_group_members()[j]:
        for l in uf.all_group_members()[j] :
            if k < l and not max(k,l) in block[min(k,l)]:
                count[k] += 1
                count[l] += 1
print(" ".join(map(str,count)))

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 c in itertools.combinations(a,2):
        # print(c)
        if set(c) in block or set(c) in friend:
            # print('pass')
            pass
        else:
            # print('suggested')
            ans[list(c)[0]] += 1
            ans[list(c)[1]] += 1

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

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 unite(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()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
s=[set() for i in range(n+1)]
parent_list=set()
for i in range(m):
  a,b=map(int,input().split())
  s[a].add(b)
  s[b].add(a)
  uf.unite(a,b)
for i in range(k):
  c,d=map(int,input().split())
  s[c].add(d)
  s[d].add(c)
for i in range(1,n+1):
  parent_list.add(uf.find(i))
ans=[0]*(n+1)
for i in parent_list:
  l=set(uf.members(i))
  v=uf.size(i)
  for j in l:
    ans[j]-=len(l&s[j])
  for j in l:
    ans[j]+=v-1
print(*ans[1:])

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 = [] + 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:
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()
        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:
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:
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,m,k = map(int,input().split())
uf = UnionFind(n)
block = {i:[] for i in range(n)}
count = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)   
    block[min(a-1,b-1)].append(max(a-1,b-1))
for i in range(k):
    c,d = map(int,input().split())
    block[min(c-1,d-1)].append(max(c-1,d-1))
for i in range(n):
    for j in range(n):
        if uf.same(i,j) and not max(i,j) in block[min(i,j)]:
            count[i] += 1
print(" ".join(map(str,count)))

Submission status: Time Limit Exceeded

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

@author: naoki
"""
from collections import deque

#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
#seen = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1].append(pair[1]-1)
    connection[pair[1]-1].append(pair[0]-1)
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
    
while False in seen:
    num+=1
    H = seen.index(False)
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo.append(i)
                seen[i] = True    
    #print(group)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1

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

Submission status: 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 unite(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()}
n,m,k=map(int,input().split())
s=set()
uf=UnionFind(n+1)
r=set()
for i in range(m):
  a,b=map(int,input().split())
  s.add((a,b))
  s.add((b,a))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  s.add((c,d))
  s.add((d,c))
for i in range(1,n+1):
  r.add(uf.find(i))
ans=[0]*(n+1)
for i in r:
  arr=uf.members(i)
  v=uf.size(i)
  for j in arr:
    for k in arr:
      if j==k:continue
      if (j,k) in s:
        ans[j]-=1
        ans[k]-=1
  for j in arr:
    ans[j]=v-1+ans[j]//2
print(*ans[1:])