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():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

    def roots(self):
        return [i for i, x in enumerate(self.root) 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)
directcount = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    directcount[a] += 1
    directcount[b] += 1
    uf.Unite(a, b)

res = []
for _ in range(n):
    res.append( [0, -1] )
ures = uf.all_group_members()

for ke in ures:
    cnt = len(ures[ke]) - 1
    for node in ures[ke]:
        res[node][0] = cnt - directcount[node]
        res[node][1] = ke


for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if res[c][1] == res[d][1]:
        res[c][0] -= 1
        res[d][0] -= 1

#print(directcount)

print(" ".join(list(map(lambda x: str(x[0]), res))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        self.roots = [{i} for i in range(size)]
    def getRootID(self, i):
        r = self.roots[i]
        if isinstance(r, set):
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return len(self.getGroupSet(i))
    def getGroupSet(self, i):
        return self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] |= self.roots[r2]
        self.roots[r2] = r1
        return True

def main():
    N,M,K=mis()
    uf = UnionFindEx(N)
    frs = tuple({i} for i in range(N))
    bls = tuple({i} for i in range(N))
    for _ in range(M):
        a, b = mis()
        uf.connect(a-1, b-1)
        frs[a-1].add(b-1)
        frs[b-1].add(a-1)
    for _ in range(K):
        a, b = mis()
        bls[a-1].add(b-1)
        bls[b-1].add(a-1)
    print(*(len(uf.getGroupSet(i) - frs[i] - bls[i]) for i in range(N)))


main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right, bisect_left
from collections import Counter, deque
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import groupby, permutations, combinations, product
from sys import stdin, stderr


# 最大公約数（ユークリッドの互除法）
# Python3.5 で math.gcd()が追加され、
# AtCoder環境と最新環境でパッケージが分かれてしまったので、自分で書いておく
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


# 拡張ユークリッド互除法
# 正整数x, y について、a*x + b*y == gcd(x,y)なるa,bを返す。
# 特に、互いに素なるx, yについては a*x + b*y == 1 となる a, b。
def exgcd(x, y):
    if y == 0:
        return 1, 0
    a, b = exgcd(y, x % y)
    return b, a - (x // y) * b


# 最小公倍数
def lcm(x, y):
    m = gcd(x, y)
    return (x // m) * (y // m)


def main():
    N, M, K = [int(x) for x in input().split()]
    edge = []
    edger = []
    for i in range(N):
        edge.append([])
        edger.append([])
    for i in range(M):
        a, b = [int(x) - 1 for x in input().split()]
        if a > b:
            a, b = b, a
        edge[a].append(b)
        edge[b].append(a)
        # edger[b].append(a)
    cluster = []
    searched = [False] * N
    c_ind = [-1] * N
    nc = 0
    cind = -1
    while nc < N:
        ind = 0
        for i in range(N):
            if not searched[i]:
                ind = i
                break
        cluster.append(set())
        cind += 1
        new_set = cluster[-1]
        unvisited = set()
        while True:
            new_set.add(ind)
            searched[ind] = True
            for x in edge[ind]:
                if not searched[x]:
                    unvisited.add(x)
            if len(unvisited) == 0:
                break
            ind = unvisited.pop()
        nc += len(new_set)
        for x in new_set:
            c_ind[x] = cind
    blocks = []
    for i in range(N):
        blocks.append([])
    for i in range(K):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].append(b)
        blocks[b].append(a)
    ret = []
    for i in range(N):
        c = cluster[c_ind[i]]
        ret.append(len(c) - len(edge[i]) - len(edger[i]) - 1)
        for b in blocks[i]:
            if b in c:
                ret[-1] -= 1
    # print(c_ind)
    return " ".join(str(x) for x in ret)


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

friends = {}
for _ in range(M):
    a, b = map(int, input().split())
    # a, b = a - 1, b - 1
    # a, b = min(a, b), max(a, b)
    if friends.get(a) is None:
        friends[a] = set([b])
    else:
        friends[a].add(b)
    if friends.get(b) is None:
        friends[b] = set([a])
    else:
        friends[b].add(a)
blocks = {}
for _ in range(K):
    a, b = map(int, input().split())
    # a, b = a - 1, b - 1
    # a, b = min(a, b), max(a, b)
    # blocks.append((a, b))
    if blocks.get(a) is None:
        blocks[a] = set([b])
    else:
        blocks[a].add(b)
    if blocks.get(b) is None:
        blocks[b] = set([a])
    else:
        blocks[b].add(a)
# print('friends', friends)
# print('blocks', blocks)


def f(c, d):
    l = friends[c]
    parents = set([c])
    # print('c, d, l', c, d, l)
    if len(l) == 0:
        return 0
    parents = parents | l
    while len(l) > 0:
        ll = set()
        for i in l:
            if d in friends[i]:
                return 1
            # print('friends[i]', friends[i])
            ll = ll | friends[i]
        ll = ll - parents
        if len(ll) == 0:
            return 0
        # print('ll', ll)
        l = ll
    return 0


ans = [0] * (N + 1)
for i in range(1, N + 1):
    if friends.get(i) is None:
        continue
    for j in range(i + 1, N + 1):
        if friends.get(j) is None:
            continue
        if i in friends[j]:
            continue
        if blocks.get(j) is not None:
            if i in blocks[j]:
                continue
        # print('i j', i, j)
        v = f(i, j)
        ans[i] += v
        ans[j] += v
for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix



def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m, k = map(int, read().split())
    friend, block = defaultdict(set), defaultdict(set)
    csr = csr_matrix((n, n), dtype=int)
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
        csr[a, b] = 1
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    _, belonging = connected_components(csr_matrix(csr))
    group = defaultdict(set)
    for i, b in enumerate(belonging):
        group[b].add(i)
    suggestion = [len(group[belonging[i]].difference(friend[i]).difference(block[i])) - 1 for i in range(n)]
    print(*suggestion)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc157/abc157_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

class Person():
    def __init__(self, i):
        self.friends = set()
        self.blocks = set()
        self.num = i
        self.group = {self}
    
    def beFriend(self, target):
        self.friends.add(target)
        target.friends.add(self)
        if id(self.group) != id(target.group):
            parent, child = (self, target) if len(self.group) > len(target.group) else (target, self)
            parent.group |= child.group
            for c in child.group:
                c.group = parent.group
    
    def beBlock(self, target):
        self.blocks.add(target)
        target.blocks.add(self)
    
    def postFriends(self):
        return self.group - self.friends - self.blocks - {self}

def main():
    N, M, K = i2nn()
    persons = [Person(i) for i in range(N)]
    for _ in range(M):
        A, B = i2nn()
        A -= 1
        B -= 1
        persons[A].beFriend(persons[B])
    for _ in range(K):
        C, D = i2nn()
        C -= 1
        D -= 1
        persons[C].beBlock(persons[D])
    #print([f.num for f in persons[0].friends])
    #print([f.num for f in persons[0].blocks])
    #print([f.num for f in persons[0].group])
    #print(*[[f.num for f in p.postFriends()] for p in persons])
    print(*[len(p.postFriends()) for p in persons])
    return

main()

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int, input().split())
f_list = [[0 for j in range(N)] for i in range(N)]
b_list = [[0 for j in range(N)] for i in range(N)]
friends = []
blocks = []
for i in range(M):
    a, b = map(int, input().split())
    f_list[a-1][b-1] += 1
    f_list[b-1][a-1] += 1
    if len(friends) == 0:
        friends.append({a,b})
    else:
        count = []
        for idx, friend in enumerate(friends):
            if (a in friend) or (b in friend):
                friends[idx] = friend.union({a,b})
                count.append(idx)
        if len(count) == 0:
            friends.append({a,b})
        elif len(count) == 2:
            idx1, idx2 = count
            assert len(friends[idx1].intersection(friends[idx2])) > 0
            friends[idx1] = friends[idx1].union(friends[idx2])
            friends.pop(idx2)
    #print(friends)
            
for i in range(K):
    a, b = map(int, input().split())
    b_list[a-1][b-1] += 1
    b_list[b-1][a-1] += 1
    
for i in range(1, N+1):
    ans = 0
    for friend in friends:
        if i in friend:
            for x in friend:
                if (f_list[i-1][x-1]!=1) and (b_list[i-1][x-1]!=1) and (i!=x):
                    ans += 1
                    #print(i,x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		frend[A].append(B)
		frend[B].append(A)
	group = []
	que = deque()
	cnt = 0
	N_ch = [-1]*N
	g = -1
	while cnt < N:
		i = N_ch.index(-1)
		que.append(i)
		g+=1
		N_ch[i]=g
		group.append(0)
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group[g]+=1
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if(N_ch[C]==N_ch[D]):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = group[N_ch[i]]-len(frend[i])-len(block[i])
		ans_v.append(ans-1)
	printH(ans_v)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, frnd, blck = map(int, input().split())
    blst = [set() for i in range(n)]
    flst = [set() for i in range(n)]
    alst = [set() for i in range(n)]
    for _ in range(frnd):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        flst[a].add(b)
        flst[b].add(a)
        alst[a] = alst[a] | alst[b] | flst[a] | flst[b]
        alst[b] = alst[a] | alst[b] | flst[a] | flst[b]
        for v in alst[a]:
            alst[v] = alst[v] | alst[b]
        for v in alst[b]:
            alst[v] = alst[v] | alst[a]
        alst[a] = alst[a] | alst[b] | flst[a] | flst[b]
        alst[b] = alst[a] | alst[b] | flst[a] | flst[b]
    for _ in range(blck):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blst[c].add(d)
        blst[d].add(c)
    for i in range(n):
        if i in alst[i]:
            alst[i].remove(i)
        for v in flst[i]:
            if v in alst[i]:
                alst[i].remove(v)
        for v in blst[i]:
            if v in alst[i]:
                alst[i].remove(v)
    for i in range(n):
        print(len(alst[i]), end="")
        if i < n:
            print(" ", end="")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
	N,M,K=map(int,input().split())
	#S=input().rstrip()
	#N=int(input())
	#vA=list(map(int,input().split()))
	vAB=[tuple(map(int,input().split()))
		 for _ in [0,]*M]
	vCD=[tuple(map(int,input().split()))
		 for _ in [0,]*K]
	
	uf = UnionFind(N)
	vF = [set() for _ in [0,]*N] # friend
	vB = [set() for _ in [0,]*N] # block
	
	for a,b in vAB:
		uf.union(a-1,b-1)
		vF[a-1] |= {b-1}
		vF[b-1] |= {a-1}
	
	for c,d in vCD:
		vB[c-1] |= {d-1}
		vB[d-1] |= {c-1}
	
	#vR = [uf.size(i)-1-vF[i]-vB[i]
	#      for i in range(N)]
	
	vR = []
	for i in range(N):
		g = uf.size(i)
		gm = uf.members(i)
		sgm = set(gm)
		#f = sum(gmm in vF[i] for gmm in gm)
		#b = sum(gmm in vB[i] for gmm in gm)
		#f = sum(ff in sgm for ff in vF[i])
		#b = sum(bb in sgm for bb in vB[i])
		f = len(sgm&vF[i])
		b = len(sgm&vB[i])
		
		vR.append(g - 1 - f - b)
		
	print(*vR)
	
main()

Submission status: Time Limit Exceeded

Solution code:
def warshallFloyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])
  return edges

def main():
    n, m, k = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = (map(int, input().split()))
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    cost = warshallFloyd(graph, n)
    for _ in range(k):
        c, d = (map(int, input().split()))
        cost[c-1][d-1] = float('inf')
        cost[d-1][c-1] = float('inf')

    ans = [0] * n
    for i in range(n):
        cost[i][i] = float('inf')
        ans[i] = (len([x for x,e in enumerate(cost[i]) if e != float('inf') and 2 <= e]))
    print(' '.join(map(str, ans)))

main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(50000)
from collections import defaultdict

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

con = defaultdict(list)
block = defaultdict(set)
friend = defaultdict(set)
for _ in range(M):
    A, B = list(map(int, input().split()))
    con[A].append(B)
    con[B].append(A)
    friend[A].add(B)
    friend[B].add(A)
for _ in range(K):
    C, D = list(map(int, input().split()))
    block[C].add(D)
    block[D].add(C)

visited = set()
group = defaultdict(set)

def dfs(node, visited, key):
    if node in visited:
        return
    group[key].add(node)
    visited.add(node)
    for next in con[node]:
        if next not in visited:
            dfs(next, visited, key)


for i in range(1, N + 1):
    dfs(i, visited, i)

ret = [0] * N
for g in group.values():
    if not g:
        continue
    size = len(g)
    for node in g:
        exclude = 0
        for blocked in block[node]:
            if blocked in g:
                exclude += 1
        for friended in friend[node]:
            if friended in g:
                exclude += 1
        ret[node - 1] = size - exclude - 1

for i in range(N):
    print(ret[i], end='')
    if i != N - 1:
        print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N, M, K = map(int, input().split())
# F = [list(map(int, input().split())) for _ in range(M)]
# B = [list(map(int, input().split())) for _ in range(K)]

F = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    F[u].add(v)
    F[v].add(u)
B = defaultdict(set)
for _ in range(K):
    u, v = map(int, input().split())
    B[u].add(v)
    B[v].add(u)

VV = defaultdict(set)
res = [0]*N
for i in range(N):
    cand = 0
    visited = [0]*N
    q = deque()
    q.append((i+1, 0))
    visited[i] = 1

    while q:
        curNode, lv = q.popleft()
        for node in F[curNode]:
            if visited[node-1] == 0 and i+1 not in VV[node-1]:
                visited[node-1] = 1
                q.append((node, lv+1))
                if lv >= 1 and i+1 not in B[node]:
                    cand += 1
                    res[i] += 1
                    VV[node-1].add(i+1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N, M, K = map(int, input().split())
edges = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

block_edges = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    block_edges[c].add(d)
    block_edges[d].add(c)

visited = [False] * N
cnt = 0

def dfs(u, s):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        if v == s:
            continue

        if v in block_edges[s] or v in edges[s]:
            pass
        else:
            global cnt
            cnt += 1

        dfs(v, s)


ans = []
for i in range(N):
    visited = [False] * N
    cnt = 0
    for v in edges[i]:
        dfs(v, i)
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = [int(x) for x in input().split()]
A = []; B = []
for _ in range(M):
    tmp1, tmp2 = [int(x) for x in input().split()]
    A.append(tmp1); B.append(tmp2)
C = []; D = []
for _ in range(K):
    tmp1, tmp2 = [int(x) for x in input().split()]
    C.append(tmp1); D.append(tmp2)

Friend = {}
for i in range(M):
    if A[i] in Friend:
        Friend[A[i]].append(B[i])
    else:
        Friend[A[i]] = [B[i]]
    if B[i] in Friend:
        Friend[B[i]].append(A[i])
    else:
        Friend[B[i]] = [A[i]]

Blocked = {}
for i in range(K):
    if C[i] in Blocked:
        Blocked[C[i]].append(D[i])
    else:
        Blocked[C[i]] = [D[i]]
    if D[i] in Blocked:
        Blocked[D[i]].append(C[i])
    else:
        Blocked[D[i]] = [C[i]]

ans = [0] * N
for i in range(N):
    checked = [0] * N   # 0:未確認, 1:本人のみ確認済, -1:自分自身
    checked[i] = -1
    que = [i + 1]
    while len(que) > 0:
        if que[0] in Friend:
            for f in Friend[que[0]]:
                if checked[f - 1] == 0:
                    checked[f - 1] = 1
                    que.append(f)
                    if i + 1 in Friend and i + 1 in Blocked:
                        if f not in Friend[i + 1] and f not in Blocked[i + 1]:
                            ans[i] += 1
                    elif i + 1 in Friend:
                        if f not in Friend[i + 1]:
                            ans[i] += 1
                    elif i + 1 in Blocked:
                        if f not in Blocked[i + 1]:
                            ans[i] += 1
                    else:
                        ans[i] += 1
        que.pop(0)

for i in range(N):
    if i != N - 1:
        print(ans[i], end= ' ')
    else:
        print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import bisect


class UnionFind():
    
    def __init__(self, n):
        self.n = next
        self.parent = [-1 for i in range(n)]
    
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        else:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parent[self.find(x)]
    
    def __str__(self):
        return str(self.parent)



def read():
    N, M, K = list(map(int, input().strip().split()))
    uf = UnionFind(N)
    friends = [list() for i in range(N+1)]
    blocked = [list() for i in range(N+1)]
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        friends[a].append(b)
        friends[b].append(a)
        uf.unite(a-1, b-1)
    for i in range(K):
        c, d = list(map(int, input().strip().split()))
        blocked[c].append(d)
        blocked[d].append(c)
    for i in range(N+1):
        friends[i] = sorted(friends[i])
        blocked[i] = sorted(blocked[i])
    return N, M, K, friends, blocked, uf


def solve(N, M, K, friends, blocked, uf):
    n_friendships = [0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if uf.same(i, j):
                fi = bisect.bisect_left(friends[i+1], j+1)
                is_friend = fi < len(friends[i+1]) and friends[i+1][fi] == j+1
                bi = bisect.bisect_left(blocked[i+1], j+1)
                is_blocked = bi < len(blocked[i+1]) and blocked[i+1][bi] == j+1
                if not is_friend and not is_blocked:
                    n_friendships[i] += 1
    return ' '.join(map(str, n_friendships))


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M,K = [int(i) for i in input().split()]
graph_fri = [[] for _ in range(N+1)]
graph_blo = [[] for _ in range(N+1)]
for i in range(M):
    A,B = [int(j) for j in input().split()]
    graph_fri[A].append(B)
    graph_fri[B].append(A)
for i in range(K):
    C,D = [int(j) for j in input().split()]
    graph_blo[C].append(D)
    graph_blo[D].append(C)
ans = [0] * N
from collections import deque
for k in range(1,N+1):
    que = deque()
    li = deque()
    seen = [False] * (N+1)
    que.append(k)
    while len(que) != 0:
        x = que.popleft()
        seen[x]=True
        for i in graph_fri[x]:
            if seen[i]:
                continue
            li.append(i)
            que.append(i)
            seen[i] = True
    li = set(list(li))
    graphA = set(graph_fri[k])
    graphB = set(graph_blo[k])
    d = li - graphA - graphB
    ans[k-1] = len(d)
print(*ans)