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:
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

edgeb=[[] for _ in range(n)]

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

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    dist_friends=[-1]*n
    dist_friends[start]=0
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1 and label[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for i in range(len(edgeb)):
    E=edgeb[i]
    for j in E:
        if label[i]==label[j]:
            Block[i]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

# for start in range(n):

#     dist_block=[-1]*n
#     dist_block[start]=0
    
#     b=deque([start])
#     while b:
#         v=b.popleft()        

#         for e in edgeb[v]:
#             if dist_block[e]==-1:
#                 dist_block[e]=dist_block[v]+1
#                 if f_can[start][e]==1 and dist_block[e]==1:
#                     f_can[start][e]=0

#                 b.append(e)


# ans=[]
# for i in f_can:
#     ans.append(sum(i))

# print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

edgeb=[[] for _ in range(n)]

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

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    dist_friends=[-1]*n
    dist_friends[start]=0
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for i in range(len(edgeb)):
    E=edgeb[i]
    for j in E:
        if label[i]==label[j]:
            Block[i]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

edgeb=[[] for _ in range(n)]

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

from collections import deque

f_can=[]
for start in range(n):
    dist_friends=[-1]*n
    dist_friends[start]=0
    d=[0]*n
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                if dist_friends[e]>1:
                    d[e]=1
                f.append(e)
    
    f_can.append(d)


for start in range(n):

    dist_block=[-1]*n
    dist_block[start]=0
    
    b=deque([start])
    while b:
        v=b.popleft()        

        for e in edgeb[v]:
            if dist_block[e]==-1:
                dist_block[e]=dist_block[v]+1
                if f_can[start][e]==1 and dist_block[e]==1:
                    f_can[start][e]=0

                b.append(e)


ans=[]
for i in f_can:
    ans.append(sum(i))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

edgeb=[[] for _ in range(n)]

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

from collections import deque






f_can=[]
for start in range(n):
    dist_friends=[-1]*n
    dist_friends[start]=0
    d=[0]*n
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                if dist_friends[e]>1:
                    d[e]=1
                f.append(e)
    
    f_can.append(d)


for start in range(n):

    dist_block=[-1]*n
    dist_block[start]=0
    
    b=deque([start])
    while b:
        v=b.popleft()        

        for e in edgeb[v]:
            if dist_block[e]==-1:
                dist_block[e]=dist_block[v]+1
                if f_can[start][e]==1 and dist_block[e]==1:
                    f_can[start][e]=0

                b.append(e)


ans=[]
for i in f_can:
    ans.append(sum(i))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [[] for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
ans = [0 for i in range(n)]
data = [0 for i in range(n)] #見たら1
for i in range(n): #自分がi
    if(data[i] != 0):
        break
    data[i] = 1
    data2 = ab[i] + [i]
    for j in ab[i]:
        data[j] = 1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = []
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0):
                    data[frfr] = 1
                    new.append(frfr)
                    data2.append(frfr)
        if(len(new)==0):
            break
        else:
            new_friends.append(new)
    for j in data2:
        count = 0
        for ano in data2:
            if(j != ano and ano not in ab[j] and ano not in cd[j]):
                count += 1
        ans[j] = count


print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [[] for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
ans = []
for i in range(n): #自分がi
    data = [0 for i in range(n)] #友人は1
    count = 0
    data[i] = 2
    for j in ab[i]:
        data[j] = 1
    for j in cd[i]:
        data[j] = -1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = []
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0):
                    data[frfr] = 1
                    new.append(frfr)
                    count += 1
                elif(data[frfr] == -1):
                    new.append(frfr)
        if(len(new)==0):
            break
        else:
            new_friends.append(new)
    ans.append(count)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [[] for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
ans = [0 for i in range(n)]
for i in range(n): #自分がi
    if(ans[i] != 0):
        break
    data = [0 for i in range(n)] #友人は1
    data[i] = 2
    data2 = ab[i] + [i]
    for j in ab[i]:
        data[j] = 1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = []
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0):
                    data[frfr] = 1
                    new.append(frfr)
                    data2.append(frfr)
        if(len(new)==0):
            break
        else:
            new_friends.append(new)
    for j in data2:
        count = 0
        for ano in data2:
            if(j != ano and ano not in ab[j] and ano not in cd[j]):
                count += 1
        ans[j] = count


print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #n個の要素を初期化
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.rank = [0] * n
    
    #木の根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    #xとyの属する集合を併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    #xとyが同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    #xが属する集合の個数
    def size(self, x):
        return self.par.count(self.find(x))
    
    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

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

N, M, K = map(int, input().split())
friends = [1]*N
blocks = [set() for _ in range(N)]
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A-1, B-1)
    friends[A-1] += 1
    friends[B-1] += 1
for _ in range(K):
    C, D = map(int, input().split())
    blocks[C-1].add(D-1)
    blocks[D-1].add(C-1)

ans = []
membersList = [[] for _ in range(N)]
for i in range(N):
    if not membersList[i]:
        members = set(uf.members(i))
        for j in members:
            membersList[j] = members
    else:
        members = membersList[i]
    members = members.difference(blocks[i])
    ans.append(len(members)-friends[i])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #n個の要素を初期化
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.rank = [0] * n
    
    #木の根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    #xとyの属する集合を併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    #xとyが同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    #xが属する集合の個数
    def size(self, x):
        return self.par.count(self.find(x))
    
    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

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

N, M, K = map(int, input().split())
friends = [1]*N
blocks = [set() for _ in range(N)]
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A-1, B-1)
    friends[A-1] += 1
    friends[B-1] += 1
for _ in range(K):
    C, D = map(int, input().split())
    blocks[C-1].add(D-1)
    blocks[D-1].add(C-1)

ans = []
for i in range(N):
    members = set(uf.members(i))
    members = members.difference(blocks[i])
    ans.append(len(members)-friends[i])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# 1457e

import sys
from sys import stdin
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

sys.setrecursionlimit(2000000)
#stdin = open("test/abc157_d_sample-1.in")

N, M, K = map(int, stdin.readline().strip().split())
f = [list(map(int, stdin.readline().strip().split())) for _ in range(M)]
b = [list(map(int, stdin.readline().strip().split())) for _ in range(K)]

G = [[0 for j in range(N)] for i in range(N)]
for f1, f2 in f:
    G[f1-1][f2-1] = 1
    G[f2-1][f1-1] = 1

n, labels = connected_components(np.array(G))

Gf = {i+1: [] for i in range(N)}
for f1, f2 in f:
    Gf[f1] += [f2]
    Gf[f2] += [f1]

Gb = {i+1: [] for i in range(N)}
for b1, b2 in b:
    Gb[b1] += [b2]
    Gb[b2] += [b1]

idx_inv = {}

for i, l in enumerate(labels):
    if l not in idx_inv.keys():
        idx_inv[l] = [i+1]
    else:
        idx_inv[l] += [i+1]

cands = []

for i in range(N):
    grp = labels[i]
    #print(grp)
    
    conn = idx_inv[grp]
    #print(conn)
    
    fr = Gf[i+1]
    #print(fr)
    
    bl = Gb[i+1]
    #print(bl)
    
    cand = set(conn) - set(fr) - set(bl) -set([i+1])
    cands += [str(len(cand))]
    
print(" ".join(cands))

Submission status: Time Limit Exceeded

Solution code:
# 1457e

def main():
    import sys
    from sys import stdin

    sys.setrecursionlimit(2000000)
    #stdin = open("test/abc157_d_sample-1.in")

    N, M, K = map(int, stdin.readline().strip().split())
    f = [set(map(int, stdin.readline().strip().split())) for _ in range(M)]
    b = [set(map(int, stdin.readline().strip().split())) for _ in range(K)]

    #print(f)
    #print(b)

    Gf = {i+1: [] for i in range(N)}
    for f1, f2 in f:
        Gf[f1] += [f2]
        Gf[f2] += [f1]

    Gb = {i+1: [] for i in range(N)}
    for b1, b2 in b:
        Gb[b1] += [b2]
        Gb[b2] += [b1]

    def dfs(Gf, Gb, Gf0, Gb0, i):
        seen[i-1]=1
        for j in Gf[i]:
            #print(i, "->", j)
            if seen[j-1]: continue
            if j not in Gf0 and j not in Gb0: n[0]+=1
            dfs(Gf, Gb, Gf0, Gb0, j)

    cand = ""

    for i in Gf.keys():
        seen = [0]*N
        n = [0]
        Gf0, Gb0 = Gf[i], Gb[i]
        dfs(Gf, Gb, Gf0, Gb0, i)
        
        cand += " "
        cand += str(max(n[0], 0))

    print(cand[1:])

main()

Submission status: Time Limit Exceeded

Solution code:
# 1457e

import sys
from sys import stdin

sys.setrecursionlimit(2000000)
#stdin = open("test/abc157_d_sample-1.in")

N, M, K = map(int, stdin.readline().strip().split())

f = [set(map(int, stdin.readline().strip().split())) for _ in range(M)]
b = [set(map(int, stdin.readline().strip().split())) for _ in range(K)]

#print(f)
#print(b)

Gf = {i+1: [] for i in range(N)}
for f1, f2 in f:
    Gf[f1] += [f2]
    Gf[f2] += [f1]

Gb = {i+1: [] for i in range(N)}
for b1, b2 in b:
    Gb[b1] += [b2]
    Gb[b2] += [b1]

def dfs(G, i):
    seen[i] = 1
    for j in G[i]:
        if seen[j]: continue
        dfs(G, j)

cand = []

for i in Gf.keys():
    #print(i)
    
    seen = {i+1: 0 for i in range(N)}
    dfs(Gf, i)
    fi = Gf[i]
    bi = Gb[i]
    #print(seen)
    #print(i, fi, bi)
    
    n = 0
    for j, s in seen.items():
        if j in fi or j in bi: continue
        n += s
    
    if n>0: n=n-1
    
    cand += [str(n)]

print(" ".join(cand))

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)
L = [set() for _ in range(N)]

for _ in range(M):
  A, B = map(lambda x: int(x)-1, input().split())
  uf.union(A, B)
  L[A].add(B)
  L[B].add(A)

for _ in range(K):
  C, D = map(lambda x: int(x)-1, input().split())
  L[C].add(D)
  L[D].add(C)

ans = []

for i in range(N):
  ans.append(len(set(uf.members(i)) - L[i]) - 1)

print(*ans)

Submission status: Time Limit Exceeded

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

friends = [[] for i in range(n)]
blocks = [[] for i in range(n)]

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

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

for i in range(n):
    j = copy.copy(friends[i])
    
    unvisited = [True] * n
    unvisited[i] = False
    for js in j:
        unvisited[js] = False
    
    block = [False] * n
    for b in blocks[i]:
        block[b] = True
    ans = 0
    
    while len(j) > 0:
        k = j.pop()
        unvisited[k] = False
        for l in friends[k]:
            if unvisited[l] is True:
                j.append(l)
                unvisited[l] = False
                if block[l] is False:
                    ans += 1
    
    print(ans, end=' ' if i != n-1 else '')

Submission status: Time Limit Exceeded

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

friends = [[] for i in range(n)]
blocks = [[] for i in range(n)]

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

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

for i in range(n):
    j = [i]
    
    unvisited = [True] * n
    block = [False] * n
    for b in blocks[i]:
        block[b] = True
    friend = [False] * n
    for f in friends[i]:
        friend[f] = True
    ans = 0
    
    while len(j) > 0:
        k = j.pop()
        unvisited[k] = False
        for l in friends[k]:
            if unvisited[l] is True:
                j.append(l)
                unvisited[l] = False
                if friend[l] is False and block[l] is False:
                    ans += 1
    
    print(ans, end=' ' if i != n-1 else '')

Submission status: Time Limit Exceeded

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

friends = [[] for i in range(n)]
blocks = [[] for i in range(n)]
not_candidates = [[i] for i in range(n)]
candidates = [0 for i in range(n)]

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

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

# print(friends)
# print(not_candidates)

for i in range(n):
    j = copy.copy(friends[i])
    while len(j) > 0:
        k = j.pop()
        for l in friends[k]:
            if l not in not_candidates[i]:
                if l not in blocks[i]:    
                    candidates[i] += 1
                j.append(l)
                not_candidates[i].append(l)
                
for i in range(n):
    print(candidates[i], end=' ' if i != n-1 else '')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
F = dict()
Block = dict()
for i in range(1, N+1):
    F[i] = []
    Block[i] = []

for _ in range(M):
    A, B = map(int, input().split())
    F[A].append(B)
    F[B].append(A)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C].append(D)
    Block[D].append(C)

def dfs(i, F):
    cnt = 0
    visited = [False]*N
    visited[i-1] = True
    deq = deque(F[i])
    while deq:
        Q = deq.pop()
        if type(Q) == int:
            Q = [Q]
        for q in Q:
            if visited[q-1]:
                continue
            visited[q-1] = True
            cnt += 1
            if q in Block[i] or q in F[i]:
                cnt -= 1
            deq += F[q]
            deq = list(set(deq))
    return cnt

for i in range(1, N+1):
    if i != N:
        print(dfs(i, F), end=' ')
    else:
        print(dfs(i, F))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
F = dict()
Block = dict()
for i in range(1, N+1):
    F[i] = []
    Block[i] = []

for _ in range(M):
    A, B = map(int, input().split())
    F[A].append(B)
    F[B].append(A)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C].append(D)
    Block[D].append(C)

def dfs(i, F):
    cnt = 0
    visited = [False]*N
    visited[i-1] = True
    deq = deque(F[i])
    while deq:
        Q = deq.pop()
        if type(Q) == int:
            Q = [Q]
        for q in Q:
            if visited[q-1]:
                continue
            visited[q-1] = True
            if q not in F[i] and q not in Block[i]:
                cnt += 1
            deq += F[q]
            deq = list(set(deq))
    return cnt

for i in range(1, N+1):
    if i != N:
        print(dfs(i, F), end=' ')
    else:
        print(dfs(i, F))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
F = dict()
Block = dict()
for i in range(1, N+1):
    F[i] = []
    Block[i] = []

for _ in range(M):
    A, B = map(int, input().split())
    F[A].append(B)
    F[B].append(A)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C].append(D)
    Block[D].append(C)

def dfs(i, F):
    cnt = 0
    visited = [False]*N
    visited[i-1] = True
    deq = deque(F[i])
    while deq:
        Q = deq.pop()
        if type(Q) == int:
            Q = [Q]
        for q in Q:
            if visited[q-1]:
                continue
            visited[q-1] = True
            if q not in F[i] and  q not in Block[i]:
                cnt += 1
            deq.append(F[q])
    return cnt

for i in range(1, N+1):
    if i != N:
        print(dfs(i, F), end=' ')
    else:
        print(dfs(i, F))

Submission status: Time Limit Exceeded

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

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

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

block = [[] for i in range(n)]
for i in range(k):
  c, d = map(int, input().split())
  c -= 1
  d -= 1
  block[c].append(d)
  block[d].append(c)

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

def dfs(s):
  vis[s] = True
  ary.append(s)
  for i in ab[s]:
    if vis[i] == False:
      dfs(i)

for i in range(n):
  vis = [False for i in range(n)]
  vis[i] = True
  x = ab[i]
  for j in x:
    vis[j] = True
  c = 0
  for j in x:
    ary = []
    dfs(j)
    ary.pop(0)
    blo = set(block[i])
    cnt = set(ary) - blo
    c += len(cnt)
  ans[i] = c
print (*ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M,K=[int(s) for s in input().split()]
A=[set() for i in range(N)]
B=[set() for i in range(N)]
for _ in range(M):
  a,b=[int(s) for s in input().split()]
  A[a-1].add(b-1)
  A[b-1].add(a-1)
for _ in range(K):
  a,b=[int(s) for s in input().split()]
  B[a-1].add(b-1)
  B[b-1].add(a-1)
A_copy=copy.deepcopy(A)
  
tree_checked=[0 for _ in range(N)]
friend_tree=[set() for _ in range(N)]

#友人関係の木
def dfs(num):
  tree=set()
  reach=[num]
  while reach:
    _from=reach.pop(-1)
    tree.add(_from)
    for _to in A[_from]:
      if not( _to in reach) and not(_to in tree):
        reach.append(_to)
        A[_to].remove(_from)
  return tree

ans=[0 for _ in range(N)]

for i in range(N):
  if tree_checked[i]==0:
    f_tree=dfs(i)
    for e in f_tree:
      tree_checked[e]=1
      friend_tree[e]=f_tree
  count=0
  for e in friend_tree[i]:
    if (e in A_copy[i]) or (e in B[i]):
      continue
    else:
      count+=1
  ans[i]=count-1

print(*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)
friend = [set([]) for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai -= 1; bi -= 1
    uf.union(ai, bi)
    friend[ai].add(bi)
    friend[bi].add(ai)

block = [set([]) for i in range(n)]
for i in range(k):
    ci, di = map(int, input().split())
    ci -= 1; di -= 1
    block[ci].add(di)
    block[di].add(ci)

dic = uf.all_group_members()
ans = [0 for i in range(n)]
for key, value in dic.items():
    shugo = set(value)
    for i in value:
        ans[i] = len(shugo-friend[i]-block[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)
friend = [set([]) for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai -= 1; bi -= 1
    uf.union(ai, bi)
    friend[ai].add(bi)
    friend[bi].add(ai)

block = [set([]) for i in range(n)]
for i in range(k):
    ci, di = map(int, input().split())
    ci -= 1; di -= 1
    block[ci].add(di)
    block[di].add(ci)

uf.all_group_members
ans = []
for i in range(n):
    ans.append(len(set(uf.members(i))-block[i]-friend[i])-1)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]


def dfs(now):
    if know[now]: return
    know[now] = 1
    for next in f[now]: dfs(next)

n,m,k = imap()
f = adj(n+1)
for i in range(m):
    a,b = imap()
    f[a].append(b)
    f[b].append(a)
ng = adj(n+1)
for i in range(k):
    c,d = imap()
    ng[c].append(d)
    ng[d].append(c)

anss = []
know = iarr(n+1)
for i in range(1,n+1):
    if know[i]: pass
    else: know = iarr(n+1); dfs(i)
    ans = sum(know) -1 #自分自身を除く
    for elm in f[i]:
        if know[elm]: ans -= 1
    for elm in ng[i]:
        if know[elm]: ans -= 1
    anss.append(ans)
print(*anss)