AtCoder Library を読んでアルゴリズムを勉強：DSU（union-find） - Qiita
競技プログラミング AtCoder では、コンテストでよく使うアルゴリズムをライブラリにした AtCoder Library (ACL) を公開していて、特に C++ ならコンテスト内で利用できます。 私は Ruby を使っているため直接は利用できず、ライブラリを模写する必要がありました。その過程で学んだアルゴリズムを整理してまとめます。 今回は disjoint set union (DSU) です。 union-find や素集合データ構造の名称のほうが一般的なようです。グラフでのイメージがしやすく、アルゴリズムも読みやすく、勉強していて楽しかった記憶があります。（ACLの模写で最初に選びました） AtCoder Library の dsu ソースコード ドキュメント 参考文献 Zvi Galil and Giuseppe F. Italiano, Data structures an
Graph Classes and Algorithms
[概要] 計算機で扱う問題は，多くの場合グラフ上の問題として定式化できる． 計算量の理論により，これまで多くの問題が``手に負えない''ことが示されてきた． 一方でこうした問題に対する現実的なアプローチがいくつか提案されてきた． 本稿ではグラフに制限を加えるアプローチについて解説する．DNA の切片間の関係などは， モデル化すると特別なグラフになる．こうしたグラフ上では， これまで手に負えないとされてきた問題が効率良く解けることがある． 本稿では，代表的なグラフクラスと，関連したアルゴリズムの最近の研究動向を解説する． [キーワード] アルゴリズム，グラフクラス，計算の複雑さ，理想グラフ [お断り] このページは，電子情報通信学会に掲載予定の同名の解説論文を加筆修正したものです． せっかく書いたので，より広く公開して，かつ，ときどきは更新して行こうかと思っています． リンクも少しずつ充実さ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
