Functional Graphテンプレ

[kemuniku]

いろいろできるとちょっと便利かもしれない 今のところやりたいこと ・サイクルへの距離(サイクルに含まれる場合は0) ・連結成分に存在するサイクルのサイクル長 ・サイクルを取得 ・x回辺の先へ移動を繰り返した後の頂点(x<=10^18)

[seekworser]

とりあえず前計算O(N)でlen_to_cycleとcycle_lenあたりを計算したい

[kemuniku]

前計算O(NlogN)かO(Nlog(10^18))かけてi個先の頂点をダブリングするやつが欲しい説もある

[kemuniku]

あとはサイクルに属しているかのboolとか？

[kemuniku]

あとはget cycleとか(O(N)でいいので)

[kemuniku]

サイクルに属しているかのboolは、サイクルまでの距離(属しているならば0)の配列の作成で対応しましょう

[kemuniku]

i頂点先ってO(N)/O(1)でできるっけ

[seekworser]

できる気がしてきた

• グラフをパスとサイクルに分離して、それぞれにIDを振る
• それぞれ頂点の並びと、パスはどのサイクルの何番目に結合するか、を持つ
• 各頂点ごとに属するパス or サイクルのIDとその中で何番目の頂点か、を持っておく

[kemuniku]

パスではなく木なのでむりじゃないかなぁになった Level Ancestor Problem がクエリO(logN)なので

[seekworser]

ごめんなさいになった

[kemuniku]

<O(n), O(1)> LAが存在するらしいです(何？)

[kemuniku]

実用上は遅いらしいのでどうしようねといった感じ 1.全部ダブリングでやる log(10^18)とかまでもつ 2.一部ダブリングでやる log(木の深さ) 3.HL分解する メモリがO(N)になります

[seekworser]

備忘 https://37zigen.com/level-ancestor-problem/

[kemuniku]

そういえばLevel Ancestor Problem って今ない？(HL分解にありましたっけ)

[seekworser]

LAはあったはず https://github.com/kemuniku/cplib/blob/96dedc8ca7273c40ba574b012fe5cfb9be7668e7/src/cplib/tree/heavylightdecomposition.nim#L138

[seekworser]

個人的には実装軽いし1でいいいかなの気持ちがあります

[kemuniku]

2もそんなには重くないと思うぜ！

[seekworser]

ﾋｨﾝ………

[kemuniku]

頂点AからBに行くことはできるか、できるなら何回の移動で行くことができるか とか