(1)問題 atcoder.jp (2)問題概要 1からNまでの番号がついたN頂点の木Gが与えられる。Gの辺を何色かで塗り分ける。一つの頂点から出る辺は全て違う色にするとき最小で何色で塗り分けられるかを求め、塗り方を一つ構築せよ。 (3)前提知識 ・N頂点の木の辺の数…

Union-Find木の書き方、使い方をまとめたUnion-Find木は、以下のことができるデータ構造である。1, 要素aと要素bのグループを併合する。 2, 要素aと要素bが同じグループに入っているか判定する。 (1)書き方 main関数の上に次のように書く class UnionFindTre…

最短経路問題におけるグラフの表現方法、BFS、ダイクストラ法、ベルマンフォード法、ワ―シャルフロイド法についてまとめた。 (1)グラフの表現方法 (1)-[1]重みなしグラフ 重みなしグラフとは、グラフの辺の重みがすべて1のグラフである。 (1)-[1]- 隣接リス…

値の追加、削除が高速にできるlistというSTLライブラリがあるらしいので使い方をまとめた。まずはlistヘッダをincludeする。 #include<list> (1)宣言 「listリスト名」で宣言する。 [例]Aという名前のint型のlistを作る。 list<int>A; (2)末尾に値を追加 「リスト名.pus</int></list>…