2023-06-06 02:15
awkで実装するUnion-Findと、ABC177 D
最近、業務時間後のオフィスで「競プロもくもくわいわい会」というのをやっている。そこで@purple_jwlさんよりUnion-Findを教えていただいたので、それをawkで実装して、ABC177のD問題を解いてみる。 Union-Findとは ここでは深く解説しないが、Union-Findについては、以下のサイトなどが参考になる。 Union-Find とは - アルゴ式 Union-Find はグループ分けを効率的に管理する、根付き木を用いたデータ構造です。 Union-Find を用いると、次の各クエリ(要求)を高速に処理できます。 N 個の要素 0,1,⋯,N−1 があり、初期状態ではそ