🟩

ABC284-E: Count Simple Paths 解説

2023/01/08に公開約500字

問題

N頂点M辺の単純無向グラフが与えられます.各頂点の次数は10以下です.
頂点1を始点とする単純パスの個数を出力してください.ただし10^6を超える場合は代わりに10^6を出力してください.
https://atcoder.jp/contests/abc284/tasks/abc284_e

解説

  • DFSを使って解く.Nが大きいので動的計画法で解きたくなる気持ちをグッと抑えよう.
  • 実際に数え上げる数は10^6以上になった時点で打ち切って良いので,DFSで数え上げることができる.
    • 既に通った頂点とパスの端を管理するとうまく数え上げることができる.
    • 既に通った頂点は参照渡しをうまく活用することでコピーを防ぐ必要がある

コード

https://atcoder.jp/contests/abc284/submissions/37865029

GitHubで編集を提案

Discussion

ログインするとコメントできます