Never Ending Journey [第七回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202107-open/tasks/past202107_j

前提知識

• DAG判定、トポロジカルソート

解説

https://atcoder.jp/contests/past202107-open/submissions/24466589

問題を簡単化しよう

都市を頂点、道路を有向辺と捉えると、全体が有向グラフの形をとる。
このように変換して考えたときに、今回の問題はループの構造がどこかにあればいくらでも旅行できるし、
そうじゃないなら旅行できないことになる。

実はこのループを持つかという問題は有名問題である。

DAG判定

有向グラフがループを持つかという部分は結構色々な所で出てくる問題で、このあたりを掘ると関連問題は多い。
ここにも色々ありますが、DAG判定あたりは初級編として良い題材と思う。

DAGというのはループが無い有向グラフのことである。
Directed acyclic graphの略なのでそのまんま。
よって、DAGであるかどうかを判定できれば、それが問題で要求されていることそのままとなる。

どうやって判定するか

競技プログラミング的にはDAG判定だけできるよりも、トポロジカルソートを学ぶ方が一石二鳥だと思うので、
トポロジカルソートを学ぶことをお勧めする。

毎回アルゴリズムを詳解していくとしんどいので、どこかで学んできてと毎回書いているが、それだと本当に今回書くことがないので、
一応オススメ資料を紹介しておく。
https://www.slideshare.net/hcpc_hokudai/topological-sort-69581002

2手法紹介されていて、どちらでも良い。
自分はdfsで実装したものをライブラリ化している。
トポロジカルソートをする過程でDAGじゃないことが判明したらDAGじゃないですよと返す実装。

多分DAG判定でググるよりもトポロジカルソートでググるほうが、競技プログラミング的な記事は多いと思う。
その辺で学んでみてほしい。
その辺が分かれば、この問題はライブラリ整備確認の問題となる。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    TopologicalSort ts(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        ts.add_edge(a, b);
    }
    
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    auto res = ts.sort(ord);

    cout << (res ? "No" : "Yes") << endl;
}