考え方 回答例 (Functional Graphであることを利用) 回答例 (UnionFind) 考え方$x$から$A_{x}$に辺を張った有向グラフを考える． グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件． この頂点の個数をカウントすれば良い．アライグマ「E問…

考え方 回答例（UnionFind） 考え方辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い． 閉路検出 - 競プロはじめました アライグマ「ABC288だったのだ！ C問題は、「辺0本から始めて、閉路にならないように何本追加できるか…

考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前が…

考え方 回答例 UnionFind DFS 考え方「$A$と$B$が隣あっている」を「$A$と$B$に辺がはられている」と読み替えればグラフの問題になる．横一列に並べられる条件は， すべての頂点から出ている辺の本数が2以下であること 閉路がないこと である．閉路検出は次…

無向グラフ UnionFind DFS 有向グラフ トポロジカルソート 無向グラフ【例】 ABC231D - Neighbors - 競プロはじめました UnionFindUnionFind（UnionFind木 - 競プロはじめました）を使えば，次で検出できる． 辺を張るたびに頂点をマージする 新たに$a,b$に…