cycle detection: "vertex disjoint" vs. "edge disjoint"

[tsutaj]

Discussion for Cycle Detection (#534)

---

Twitter で「https://judge.yosupo.jp/problem/cycle_detection は辺素・あるいは点素のサイクルを求めているのか？」という具合に少し議論になったので書いてます。会話を追いたい人は https://twitter.com/beet_aizu/status/1283410149370023936 とそのリプライも参照してください。

現状は 辺素な サイクルを求める問題設定になっており、点素なサイクルを求める問題はありません。これについてどのように対処すべきかを決定したいです。案としては大きく分けて 3 つあると思います。

1. (適用済み) 現在の問題を、辺素であることが分かりやすいように表現を変える
   • pull request #543
2. 点素と辺素、どちらの問題も作る
3. 現在ある問題を点素の設定に差し替え、辺素は作らない
   • 理由: 点素サイクル発見は辺素サイクル発見を兼ねるため

なお、今ある問題のコードをほぼそのまま流用できることから、どちらの案を採用したとしても作業量は少ないです。

---

Now, the Cycle Detection task requires that "you have to find edge-disjoint cycle", so there are no tasks which require you of finding vertex-disjoint cycle. I want to decide how to deal with this issue. I think there are three types of solutions.

1. (applied) Change the representation of the current problem so as to make it easier to realize that it is "edge-disjoint problem", and provide edge-disjoint task only
   • pull request #543
2. Make both problems (edge-disjoint, and vertex-disjoint)
3. Replace current edge-disjoint task with vertex-disjoint task (and delete edge-disjoint task)
   • the reason: If you have a solution for vertex-disjoint task, this is also a soluiton for edge-disjoint task.

The workload is very small whichever we choose. (don't worry)

[yosupo06]

一連の流れを追いました、このライブラリで出題できうる閉路検出は3つ、「点素」「辺素」「制限なし + ただし出力長制限10^6」 の3つがあると思います。ここで「制限なし + ただし出力長制限10^6」は不自然なので、特段の理由がなければ「点素」、「辺素」のどちらかになると思います。

個人的にはどちらを選んでも不自然ではない=今の状態はそんなに変ではないので、特段の需要がないならば変更しなくていいのではと思います

[tsutaj]

そのままでいく、という基本的な案をわすれていました・・・ 冷静に考えて 1 がそれですね

需要があれば作ろうと思いますが (ある人はそのように書いてほしい)、なければこのままでいいと自分も思います