ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Union-Find木

ABC065 D - Built?

問題 提出コード 解法 考察でごり押したら最小全域木とかいうやつを使っていたみたいです。 初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。 ですが、実は本程度まで減らすことができます。 個の座標をxについてソートした場合の隣り…

ARC065 D - 連結 / Connectivity

問題 提出コード 解法 UnionFind木を貼ると解ける問題です。 鉄道について、辺をそのままUnionFind木に反映させると、根が同じ都市については、連結であることになります。 道路についても同様です。ということで、まずはUnionFind木を2つ用意し、鉄道と道路…