Edit

【pythonでABC204を解説】C - Tour

問題概要

問題ページ

C - Tour
C - Tour

問題ページへ移動する

問題文

AtCoder 国には \(1\) から \(N\) の番号がついた \(N\) 個の都市と、\(1\) から \(M\) の番号がついた \(M\) 個の道路があります。

道路 \(i\) を通ると都市 \(A_i\) から \(B_i\) へ移動することができます。都市 \(B_i\) から都市 \(A_i\) への通行はできません。

ピューマは、どこかの都市からスタートし、\(0\) 本以上の道路を使い移動して、どこかの都市をゴールとするような旅行の計画を立てようとしています。

スタート地点とゴール地点の都市の組として考えられるものは何通りありますか？

制約

  • \(2 \leq N \leq 2000\)
  • \(0 \leq M \leq \min(2000,N(N-1))\)
  • \(1 \leq A_i,B_i \leq N\)
  • \(A_i \neq B_i\)
  • \((A_i,B_i)\) は相異なる
  • 入力に含まれる値は全て整数である

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    edges = [[] for _ in range(n)]
    for i in range(m):
        edge_a, edge_b = list(map(int, input().rstrip('\n').split()))
        edges[edge_a-1].append(edge_b-1)

    c = 0
    for i in range(n):
        ql = [[0, i]]
        ql = collections.deque(ql)
        fq = collections.defaultdict(int)
        fq[i]
        c += 1
        while ql:
            cost, now_edge = ql.popleft()
            for next_edge in edges[now_edge]:
                if next_edge not in fq:
                    ql.append((cost + 1, next_edge))
                    fq[next_edge]
                    c += 1
    print(c)


if __name__ == '__main__':
    solve()

-Edit