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:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        block[c].append(d)
        block[d].append(c)

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            s = [k_ for k_ in stack[tree] if not k_ in check_list]
            candidates[k] = len(s)

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        block[c].append(d)
        block[d].append(c)

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            for k_ in stack[tree]:
                if not k_ in check_list:
                    candidates[k] += 1

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map( int, input().split() )
friends = [ set() for _ in range( N + 1 ) ]

for i in range( M ):
  a, b = map( int, input().split())
  friends[ a ].add( b )
  friends[ b ].add( a )

friends_chain = []

sets = set( range( 1, N + 1) )

while sets != set():
  i = sets.pop()
  lists = [ i ]
  chain = { i }
  while lists != []:
    j = lists.pop()
    lists += list( friends[ j ] - chain )
    chain |=  friends[ j ]
  friends_chain.append( chain )
  sets -= chain

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

ans=""
for i in range( 1, N + 1 ):
    for u in friends_chain:
        if i in u:
            ans += str( len( u - friends[i] - block[i] - { i } ))
            break
    if i != N:
      ans += " "
print( ans )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

class prof:
    def __init__(self, num):
        self.num = num
        self.friends = []
        self.blocks = []        
        self.clus = -1
        self.ca = 0

    def set_friends(self, fre):
        self.friends.append(fre)

    def set_blocks(self, blo):
        self.blocks.append(blo)

    def set_clus(self, cl):
        self.clus = cl
    
    def set_ca(self, c):
        self.ca = c



def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    nodes = [prof(i) for i in range(N)]

    for ai, bi in zip(A, B):
        nodes[ai-1].set_friends(bi)
        nodes[bi-1].set_friends(ai)
    for ai, bi in zip(C, D):
        nodes[ai-1].set_blocks(bi)
        nodes[bi-1].set_blocks(ai)
    
    prof_l = set(list(range(1,N+1)))
    done_l = []
    q = []
    c_num = 0

    while len(done_l) != N:
        # print("len done : {}".format(len(done_l)))
        # print(done_l)
        q.append((prof_l - set(done_l)).pop())
        while (len(q)) > 0:
            p_nm = q.pop(0)
            nodes[p_nm-1].set_clus(c_num)
            done_l.append(p_nm)

            add_q = list(set(nodes[p_nm-1].friends) - set(done_l))
            q.extend(add_q)
            q = list(set(q))
        c_num += 1
        done_l = list(set(done_l))

    # print([x.clus for x in nodes])

    clus_s = [[] for _ in range(c_num)]
    for i, x in enumerate(nodes):
        clus_s[x.clus-1].append(i+1)

    clus_s = [set(x) for x in clus_s]
    # print(clus_s)
    # print(c_num)
    for cs_i in range(c_num):
        cs = clus_s[cs_i]
        for c in cs:
            nodes[c-1].set_ca(len(cs - set(nodes[c-1].blocks) - set(nodes[c-1].friends)) -1 )

    print(*[x.ca for x in nodes])



    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, M, K = map(int, input().split())
    from heapq import heappush, heappop

    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E = N, M + K  # 頂点数、辺の数、始点
    g = [[] for i in range(V)]  # 隣接リスト

    for i in range(M):
        s, t = map(int, input().split())
        g[s - 1].append((1, t - 1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((1, s - 1))
    blocks = [[False] * N for i in range(N)]
    for i in range(K):
        s, t = map(int, input().split())
        g[s - 1].append((10 ** 10, t - 1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((10 ** 10, s - 1))
        blocks[s - 1][t - 1] = True
        blocks[t - 1][s - 1] = True

    INF = 10 ** 10
    for n in range(N):
        sum = 0
        ind = 0
        for i in dijkstra(V, g, n):
            if blocks[n][ind] == False and i != 0 and i != 1 and not i >= 10 ** 10:
                sum += 1
            ind += 1
        print(sum, end=' ')
    print()


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,M,K=map(int,input().split())
    from heapq import heappush, heappop

    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E= N,M+K # 頂点数、辺の数、始点
    g = [[] for i in range(V)] # 隣接リスト

    for i in range(M):
        s, t= map(int, input().split())
        g[s-1].append((1, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((1, s - 1))
    blocks=[[False]*N for i in range(N)]
    for i in range(K):
        s, t= map(int, input().split())
        g[s-1].append((10**10, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t- 1].append((10**10, s - 1))
        blocks[s-1][t-1]=True
        blocks[t-1][s-1]=True



    INF = 10 ** 16
    for n in range(N):
        sum=0
        ind=0
        for i in dijkstra(V, g, n):
            if blocks[n][ind]==False and i != INF and i!=0 and i!=1 and not i>=10**10:
                sum+=1
            ind+=1
        print(sum, end=' ')
    print()

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,M,K=map(int,input().split())
    from heapq import heappush, heappop

    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E= N,M+K # 頂点数、辺の数、始点
    g = [[] for i in range(V)] # 隣接リスト

    for i in range(M):
        s, t= map(int, input().split())
        g[s-1].append((1, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((1, s - 1))
    blocks=[[False]*N for i in range(N)]
    for i in range(K):
        s, t= map(int, input().split())
        g[s-1].append((10**10, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t- 1].append((10**10, s - 1))
        blocks[s-1][t-1]=True
        blocks[t-1][s-1]=True



    INF = 10 ** 20
    for n in range(N):
        sum=0
        ind=0
        for i in dijkstra(V, g, n):
            if blocks[n][ind]==False and i != INF and i!=0 and i!=1 and not i>=10**10:
                sum+=1
            ind+=1
        print(sum, end=' ')
    print()

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,M,K=map(int,input().split())
    from heapq import heappush, heappop

    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E= N,M+K # 頂点数、辺の数、始点
    g = [[] for i in range(V)] # 隣接リスト

    for i in range(M):
        s, t= map(int, input().split())
        g[s-1].append((1, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((1, s - 1))
    blocks=[[] for i in range(N)]
    for i in range(K):
        s, t= map(int, input().split())
        g[s-1].append((10**10, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t- 1].append((10**10, s - 1))
        blocks[s-1].append(t-1)
        blocks[t-1].append(s-1)




    INF = 10 ** 20
    for n in range(N):
        sum=0
        ind=0
        for i in dijkstra(V, g, n):
            if ind not in blocks[n] and i != INF and i!=0 and i!=1 and not i>=10**10:
                sum+=1
            ind+=1
        print(sum, end=' ')
    print()

resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue
stack = queue.LifoQueue()

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

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

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

seen = [False]*n
group = [-1]*n
G = []

def dfs(v):
    global start
    seen[v] = True
    group[v] = start
    graph.append(v)
    stack.put(v)
    while stack.qsize() != 0:
        x = stack.get()
        for i in friend[x]:
            if seen[i]:
                continue
            seen[i] = True
            group[i] = start
            graph.append(i)
            stack.put(i)

start = 0
for i in range(n):
    if seen[i] == False:
        graph = []
        dfs(i)
        start += 1
        G.append(graph)

group_sum = []
for j in set(group):
    group_sum.append(group.count(j))

#print(G)
#print(group)
#print(group_sum)

c_list = []
for k in range(n):
    c = group_sum[group[k]] - len(set(G[group[k]]) & set(friend[k] + block[k])) - 1
    c_list.append(c)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

friend = defaultdict(set)
block  = defaultdict(set)
dp = {}

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

for i in range(m):
  a, b = map(int, input().split())
  friend[a] |= {b}
  friend[b] |= {a}
for i in range(k):
  a, b = map(int, input().split())
  block[a] |= {b}
  block[b] |= {a}

def find(node):
  if node in dp:
    seen = dp[node]
  else:
    seen = set([node])
    q = set([node])
    while q != set():
      next_q = set()
      for i in q:
        for n in filter(lambda x: x not in seen, friend[i]):
          next_q |= {n}
        seen |= friend[i]
      q = next_q
    for n in seen:
      dp[n] = seen
  cands = seen - {node} - block[node] - friend[node]
  return len(cands)

print(' '.join(str(find(i)) for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

friend = defaultdict(set)
block  = defaultdict(set)

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

for i in range(m):
  a, b = map(int, input().split())
  friend[a] |= {b}
  friend[b] |= {a}
for i in range(k):
  a, b = map(int, input().split())
  block[a] |= {b}
  block[b] |= {a}

def find(node, before):
  seen = set([node])
  q = set([node])
  while q != set():
    next_q = set()
    for i in q:
      for n in filter(lambda x: x not in seen, friend[i]):
        next_q |= {n}
      seen |= friend[i]
    q = next_q
  cands = seen - {node} - block[node] - friend[node]
  return len(cands)

print(' '.join(str(find(i, 0)) for i in range(1, n+1)))

Submission status: Time Limit Exceeded

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Time Limit Exceeded

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        next = next_stack.pop(-1)
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Time Limit Exceeded

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Time Limit Exceeded

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

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

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = set([i])
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = list(friends_table[i])
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend.add(next)
        group_list[next] = i
        next_stack += list(friends_table[next])
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(friends_candidate[i].difference(friends_table[i]|blocks_table[i]))-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([Node(i) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  total_done_set = set()

  def dfs(node, done_set):
    if node.id in done_set: return 0

    total_done_set.add(node.id)
    done_set.add(node.id)

    size = 1
    for child in node.children:
      size += dfs(child, done_set)

    return size


  ans_list = [-1] * n

  def dfs2(node, connected_ids, total_len):
    ans_list[node.id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    except_num = 0
    for child in node.children:
      if child.id not in node.block_id_set:
        except_num += 1

      if ans_list[child.id] == -1:
        dfs2(child, connected_ids, total_len)

    ans_list[node.id] -= except_num


  for base_node in nodes:
    if base_node.id not in total_done_set:
      done_set = set()
      dfs(base_node, done_set)
      dfs2(base_node, done_set, len(done_set))

  print(*ans_list, sep=" ")


main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([Node(i) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  total_done_set = set()

  def dfs(node, done_set):
    if node.id in done_set: return 0

    total_done_set.add(node.id)
    done_set.add(node.id)

    for child in node.children:
      node.size += dfs(child, done_set)

    return node.size


  ans_list = [0] * n

  def dfs2(node, done_set, connected_ids, total_len):
    node_id = node.id
    if node_id in done_set: return 0

    done_set.add(node_id)

    ans_list[node_id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    except_num = 0

    for child in node.children:
      if child.id not in node.block_id_set:
        except_num += 1

      dfs2(child, done_set, connected_ids, total_len)

    ans_list[node_id] -= except_num


  for base_node in nodes:
    if base_node.id not in total_done_set:
      done_set = set()
      dfs(base_node, done_set)
      dfs2(base_node, set(), done_set, len(done_set))

  print(*ans_list, sep=" ")


main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = {i: Node(i) for i in range(n)}
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  def dfs(node, done_set):
    if node.id in done_set: return 0

    nodes.pop(node.id)
    done_set.add(node.id)

    for child in node.children:
      node.size += dfs(child, done_set)

    return node.size


  ans_list = [0] * n

  def dfs2(node, done_set, connected_ids):
    if node.id in done_set: return 0

    done_set.add(node.id)

    ans_list[node.id] = len(connected_ids) - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    for child in node.children:
      if child.id not in node.block_id_set:
        ans_list[node.id] -= 1

      dfs2(child, done_set, connected_ids)

  while nodes:
    for node in nodes.values():
      done_set = set()
      dfs(node, done_set)
      dfs2(node, set(), done_set)
      break

  print(*ans_list, sep=" ")


main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([Node(i) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  total_done_set = set()

  def dfs(node, done_set):
    if node.id in done_set: return 0

    total_done_set.add(node.id)
    done_set.add(node.id)

    for child in node.children:
      node.size += dfs(child, done_set)

    return node.size


  ans_list = [0] * n

  def dfs2(node, done_set, connected_ids):
    if node.id in done_set: return 0

    done_set.add(node.id)

    ans_list[node.id] = len(connected_ids) - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    for child in node.children:
      if child.id not in node.block_id_set:
        ans_list[node.id] -= 1

      dfs2(child, done_set, connected_ids)


  for base_node in nodes:
    if base_node.id not in total_done_set:
      done_set = set()
      dfs(base_node, done_set)
      dfs2(base_node, set(), done_set)

  print(*ans_list, sep=" ")


main()

Submission status: Time Limit Exceeded

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

S = [set() for i in range(N)]

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

UFT = UnionFind(N)

for _ in range(M):
    A, B = map(int,input().split())
    S[A-1].add(B-1)
    S[B-1].add(A-1)
    UFT.union(A-1,B-1)
for _ in range(K):
    C, D = map(int,input().split())
    S[C-1].add(D-1)
    S[D-1].add(C-1)

ans = []
for i in range(N):
    ans.append(UFT.size(i) - len(UFT.members(i) & S[i]) - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
import sys
rks = [None] *n
sys.setrecursionlimit(10**9)
fgraph = [list() for i in range(n)]
bgraph = [list() for i in range(n)]
cgraph = [list() for i in range(n)]
for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)
def dfs(graph,s,r):
    if rks[s] is None:
        rks[s] = r
    for i in range(len(graph[s])):
        if rks[graph[s][i]-1] is not None:
            continue
        dfs(graph, graph[s][i]-1,r)
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)
for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)
for i in range(n):
        print(rks.count(rks[i]) - len(fgraph[i]) - len(bgraph[i]) - 1)