GCDGraph TopCoder グラフに置ける２点間に経路があるか否か
問題URL
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 only if gcd(i, j) > k. Here, gcd(i, j) denotes the greatest common divisor of i and j.
The s x and y are the numbers of two (not necessarily distinct) vertices in our graph. Return "Possible" if it is possible to travel from x to y by following the edges of our graph. Otherwise, return "Impossible".
In other words, return "Possible" if our graph contains a path that connects the nodes x and y, and "Impossible" if there is no such path.
Definition
Class: GCDGraph Method: possible Parameters: int, int, int, int Returns: String Method signature: String possible(int n, int k, int x, int y) (be sure your method is public)
Constraints
- n will be between 2 and 1,000,000, inclusive.
- k will be between 0 and n, inclusive.
- x and y will be between 1 and n, inclusive.
要約
N個のノードが与えられ、それぞれのノードには整数i(1 <= i <= N)が振られている。頂点i, jにおいて、i, jの最大公約数がkより大きければi, j間を繋げる。このようにして作成されるグラフにおいて、与えられる頂点x, y間には経路が存在するか否かという問題。
解法
「与えられた２点間x, yに経路が存在するか」という問いは「xのルートノードとyのルートノードは一致するか」という問に変更できる。経路が存在するとうことは２つの頂点は同じグラフに属しているからだ。これを高速に算出するためにUnion-Findという手法を用いる。
Union-Findとは
Union-Findとは、結合(Union)とルートノードを探す(Find)の２つの操作を用いて、任意のノードのルートノードを取得するためのアルゴリズムである。これを応用して２つのノードが同じグラフに属しているかを判定することができる。
詳しくは以下を参照。
keita-matsushita.hatenablog.com
最大公約数を工夫して算出する
全ての頂点i, jに対して最大公約数を求めようとするとNが最大106なので間に合わない。そこで以下のような手段を取る。
詳しく見てみる。最大公約数を固定しgcdと名付ける。gcdの倍数を「i」と名付けた時に、gcdとiの最大公約数は必ずgcdとなる。 つまり、gcdとi間は必ず経路が存在し辺を渡す事ができる。固定したgcdをK < gcd <= Nまで行うことで、全てのパターンを満たす事ができる。
