Ryotaro Sato

[Pebble Game Algorithms and (k, l)-Sparse Graphs](https://www.emis.de/journals/DMTCS/pdfpapers/dmAE0136.pdf) に載っていそう [Matroid oracle - Wikipedia](https://en.wikipedia.org/wiki/Matroid_oracle) の実装について 頂点側を $k$ 倍に拡張して辺側と 2 部マッチングする - Circuit-find oracle - あらかじめ独立集合 $F \subseteq E$ がセットされる - DM 分解しておく...

[Pebble Game Algorithms and (k, l)-Sparse Graphs](https://www.emis.de/journals/DMTCS/pdfpapers/dmAE0136.pdf) 本質的には最大二部マッチングを交互道でやっているやつと同じに見えるが、定数倍が軽く一般化も楽に見えるので実装方針はこれがよさそう？ [Finding and Maintaining Rigid Components](https://scholarworks.smith.edu/cgi/viewcontent.cgi?article=1246&context=csc_facpubs) データ構造を頑張るやつ component が管理できる？

まあまあ https://atcoder.jp/contests/tessoku-book/submissions/38355569

https://atcoder.jp/contests/abc256/submissions/35143180 というふうに実装したら早くなったが、https://yukicoder.me/submissions/800244 に適用したらむしろ遅くなる。 F 同士の合成、S への F の作用、S 同士のマージの相対的な計算量に応じて最適な実装が決まりそうで、うまい抽象化がわからず困る。

そもそも適切に実装したら通るので close します。

https://yukicoder.me/problems/no/2452

Trie で特にパスの場合として捉えると長さ N + 1 の列のままの方が自然な気がしてきた

https://qoj.ac/contest/1223/problem/6409 https://github.com/hitonanode/cplib-cpp/issues/295 とまとめてもよさそう

#177

Verify 問 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1377