~/algor $ cat masalalar/bogliqlik-komponentalari
Graf-01
Bog'liqlik komponentlari soni
Muallif:
Iqbolshoh Ilhomjonov
Oson
1000 ms
128 MB
26%
$n$ ta cho'qqi va $m$ ta qirradan iborat yo'naltirilmagan graf berilgan. Cho'qqilar $1$ dan $n$ gacha raqamlangan. Grafdagi bog'liqlik komponentalari — bir-biriga yo'l orqali bog'langan cho'qqilar guruhlari sonini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: $n$ va $m$. Keyingi $m$ ta qatorning har birida ikkita natural son: $u$ va $v$ — qirra tutashtirgan cho'qqilar.
Chiquvchi ma'lumotlar
Bitta butun son — komponentalar soni.
Izoh
$1 \le n \le 10^{5}$
$0 \le m \le 2 * 10^{5}$
$1 \le u, v \le n$
Grafda karrali qirralar va halqalar bo'lishi mumkin.
Misollar
Kirish #1
5 4 1 2 2 3 1 3 4 5
Chiqish #1
2
Kirish #2
4 0
Chiqish #2
4