連結 Scala編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

ここからは、最小全域木問題を解くクラスカル法の実装をゴールに、ユニオンファインド木を用いて問題を解いていきましょう。

1, ..., n の番号のついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

m 本の枝が与えられます。与えられた枝集合から構成されるグラフが連結かどうか判定してください。ただし、グラフが連結とは、任意の 2 頂点間に路が存在している（枝をたどって到達できる）ことです。

入力される値

n m
a_1 b_1
...
a_m b_m

・ 1 行目に、頂点の個数を表す n と、枝の本数を表す m が与えられます。
・ i + 1 行目に、枝 i を表す頂点の組 (a_i, b_i) が与えられます。(1 ≦ i ≦ m)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 構成されたグラフが連結ならば Yes、そうでなければ No と 1 行で出力してください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100
・ 1 ≦ m ≦ n(n-1) / 2
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・同じ頂点の組は 2 回以上入力されない

入力例1: 4 6
1 2
1 3
1 4
2 3
2 4
3 4

出力例1: Yes

入力例2: 6 6
1 2
1 3
2 3
4 5
4 6
5 6

出力例2: No

問題一覧へ戻る