AT_unionfind_a Union Find

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/unionfind_a この問題は、講座用問題です。ページ下部に解説が掲載されています。 $ N $ 頂点の、単純とは限らない無向グラフを考えます。 初期状態では、頂点のみが存在し、辺は全く存在せず、全ての頂点が孤立しているとします。 以下の $ 2 $ 種類のクエリが、$ Q $ 回与えられます。 - 連結クエリ： 頂点 $ A $ と、頂点 $ B $ を繋ぐ辺を追加します。 - 判定クエリ： 頂点 $ A $ と、頂点 $ B $ が、連結であるかどうか判定します。連結であれば `Yes`、そうでなければ `No` を出力します。 クエリを順番に処理し、判定クエリへの回答を出力して下さい。 この際、同じ辺が何度も追加されることや、自分自身への辺が追加されることもある事に注意してください。 連結であるとは、頂点 $ A $ から頂点 $ B $ まで辺をたどって到達可能であることを意味します。 $ A $ と $ B $ が同じ頂点の場合、連結であると定義します。 グラフは無向であるため、連結クエリによって頂点 $ A,\ B $ 間の辺が追加されると、$ A $ から $ B $ へも $ B $ から $ A $ へも辿れるようになります。

N/A

N/A

### 解説 **[Union find(素集合データ構造)](https://www.slideshare.net/secret/CIWAduFPvzGrrE "Union find(素集合データ構造)")** from **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### Sample Explanation 1 以下のような手順で実行されます。 - $ 1 $ つ目のクエリで、頂点 $ 1 $ と頂点 $ 2 $ を繋ぎます。 - $ 2 $ つ目のクエリで、頂点 $ 3 $ と頂点 $ 2 $ を繋ぎます。 - $ 3 $ つ目のクエリで、頂点 $ 1 $ と頂点 $ 3 $ の連結判定を行います。連結しているので、`Yes`と出力します。 - $ 4 $ つ目のクエリで、頂点 $ 1 $ と頂点 $ 4 $ の連結判定を行います。連結していないので、`No`と出力します。 - $ 5 $ つ目のクエリで、頂点 $ 2 $ と頂点 $ 4 $ を繋ぎます。 - $ 6 $ つ目のクエリで、頂点 $ 4 $ と頂点 $ 1 $ の連結判定を行います。連結しているで、`Yes`と出力します。 - $ 7 $ つ目のクエリで、頂点 $ 4 $ と頂点 $ 2 $ を繋ぎます。これらは既に繋がれていますが、多重辺が出来ることもあります。 - $ 8 $ つ目のクエリで、頂点 $ 0 $ と頂点 $ 0 $ を繋ぎます。これらは同じ頂点ですが、自己ループが出来ることもあります。 - $ 9 $ つ目のクエリで、頂点 $ 0 $ と頂点 $ 0 $ の連結判定を行います。同じ頂点は常に連結していると見做せるので、`Yes`と出力します。