No.9017 ac-library 動作確認
問題文最終更新日: 2026-09-07 01:23:29
問題文
$N$ 頂点 $M$ 辺の無向グラフがあります。頂点には $0$ から $N-1$ までの番号が付いています。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。
このグラフの連結成分の個数を出力してください。
この問題は、yukicoder のジャッジ環境で ac-library (AtCoder Library) の各言語版が使えることを確かめるためのものです。 言語ごとの読み込み方は ジャッジ環境のヘルプ にあります。
入力
入力は次の形式で与えられます。
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
制約
- 入力される値はすべて整数
- $1 \le N \le 10^5$
- $0 \le M \le 2 \times 10^5$
- $0 \le u_i, v_i \le N-1$
- $u_i = v_i$ となる辺(自己ループ)や、同じ頂点の組を結ぶ辺が複数あること(多重辺)もある
出力
連結成分の個数を $1$ 行に出力してください。 出力の最後には改行を入れてください。
サンプル
サンプル1
入力
5 3 0 1 1 2 3 4
出力
2
連結成分は $\{0, 1, 2\}$ と $\{3, 4\}$ の $2$ つです。
サンプル2
入力
1 0
出力
1
辺が $1$ 本もないので、頂点 $0$ だけからなる連結成分が $1$ つです。
サンプル3
入力
4 5 0 1 1 2 2 3 3 0 1 1
出力
1
自己ループや多重辺があっても答えは変わりません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。