UnionFind
考え方 回答例 (Functional Graphであることを利用) 回答例 (UnionFind) 考え方$x$から$A_{x}$に辺を張った有向グラフを考える． グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件． この頂点の個数をカウントすれば良い．アライグマ「E問…
考え方1 考え方2 考え方1閉路ができたかどうかをUnionFind木で見る（閉路検出 - 競プロはじめました）． N, M = map(int, input().split()) # --- UnionFind --- p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def …
考え方 回答例 考え方UnionFind木（UnionFind木 - 競プロはじめました）で辺で結ばれる頂点をマージする．辺の数は，UnionFind木の親に対応付けて管理する．回答例 N, M = map(int, input().split()) E = [] for _ in range(M): u, v = map(int, input().spl…
考え方 回答例（UnionFind） 考え方辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い． 閉路検出 - 競プロはじめました アライグマ「ABC288だったのだ！ C問題は、「辺0本から始めて、閉路にならないように何本追加できるか…
考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前が…
考え方 回答例 考え方すべての点の組み合わせをみて，隣接しているものをUnionFind（UnionFind木 - 競プロはじめました）でマージすれば良い．2点$(x_{1}, y_{1}), (x_{2}, y_{2})$の隣接条件は\begin{aligned} \begin{cases} \, \max(|x_{1} - x_{2}|, |y_{…
考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…
考え方 回答例 考え方$0$$,1, 2, ..., N$を頂点とするグラフで考える．「$(l, r)$が与えられる」を「頂点$(l - 1)$と頂点$r$の間に（無向）辺が張られる」と読み替えれば，\begin{aligned} & a_{1} + a_{2} + \cdots a_{N} \text{が計算できる} \\ &\Leftrig…
最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…
用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…
考え方 回答例 参考 考え方連結成分ごとの答えをかけ合わせれば良い．「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」とき，頂点と辺は1セットと考えることができ (頂点数) = (辺数) という条件を満たす．また，「(頂点…
無向グラフ UnionFind DFS 有向グラフ トポロジカルソート 無向グラフ【例】 ABC231D - Neighbors - 競プロはじめました UnionFindUnionFind（UnionFind木 - 競プロはじめました）を使えば，次で検出できる． 辺を張るたびに頂点をマージする 新たに$a,b$に…
【関連記事】 UnionFind木 - 競プロはじめました 考え方 回答例 考え方逆から考えてUnionFind木でつないでいくだけ．連結成分の数は， 頂点を加えたら+1 つながっていないグループを新たにつないだら-1 とすればよい．グラフの辺は小さい頂点から大きい頂点…
【関連】 UnionFind木 - 競プロはじめました 考え方 回答例 考え方$2^{10} = 1024$だから，$N= 2^{20}\simeq 10^{6}$．操作で時間がかかるのは$t_{i} = 1$の2. の部分．これを高速化するには，与えられた$x_{i}$に対しx[i] += 1$\pmod{N}$を繰り返し，はじめ…
実装 基本形 例題 AtCoder Typical Contest 001 参考 実装基本形 p = [-1] * (N + 1) # 親の配列 (いなければ-1), N要素 (1-indexed, P[0]はダミー) def root(x): # 親がいなければ自分(=根)を返す if p[x] < 0: return x # 自分の根 = 親の根 # & パス圧縮 …
C++ ではこんなに簡単にかけるのに．．． Editorial - AtCoder Beginner Contest 217【追記（C++ の回答）】(C++) ABC217D - Cutting Woods - 競プロはじめました一般的な話は次が役立ちそう： std::setを使わない代替テクニック [いかたこのたこつぼ] 【Pyt…
