Union-Find

GCDGraph TopCoder グラフに置ける2点間に経路があるか否か

問題URL arena.topcoder.com Problem Statement You are given four s: n, k, x, and y. The s n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and…

Union-Findを用いてそれぞれの木の大きさを高速で求める

問題 D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder 解法 Union-Findを用いて、それぞれの国民の持つ条件によって作成される木(都市と道路の関係図)の大きさ(都市数)を求める。 Union-Findとは 木が持つ情報(高さ、大きさ、どの要…

Union-Findを用いて2つの要素が同じ集合に属してるかを高速で判定する

Union-Findとは Union-Findとは、2つの要素が同じ集合に属しているか否かを高速で判定することを実現するデータ構造である。Union−Findは、様々な実装パターンが存在するが木構造を用いた物を考える。また、Union-Findはその名前からも分るように以下の2つ…