問題一覧 > 教育的問題

No.9017 ac-library 動作確認

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 1
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 13954 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。