Qrafiklər üçün çox yayılmış bir üsul...
Vitaliy Qoldşteyn Qış Məktəbində qraflar, ağ, qara və boz zirvələr, qraflar üzərində bir çox məsələlərin dərinlik axtarışı metodu ilə həlli haqqında danışırdı. Söhbətin sonunda isə proqramçının çətin həyatı haqqında danışmağa başladı və 2011-ci ildə Xarkovda Qış Məktəbində hamıya daha bir məsələnin verilməsini unutdu, hansı ki, göstərilən metodla həll edilə bilər. Əlbəttə, Vitaliy onu unuda bilməzdi və bizdən bu məsələnin hamıya təklif edilməsini xahiş etdi, çünki əsl usta-lektor kimi o, auditoriya ilə istənilən ünsiyyətdə, hətta bu ünsiyyət məsafədən baş verirsə belə, sadə də olsa, hansısa bir məsələni vermək imkanını qaçırmamalıdır.
Beləliklə, onun dərinlik axtarışı metodu ilə həll edilən daha bir sadə məsələsi belə səslənir: “Sizə N zirvələri və M kənarları olan istiqamətsiz qraf verilir (1 ≤ N ≤ 20000, 0 ≤ M ≤ 200000). Qrafda döngələr və çoxlu kənarlar yoxdur. Verilmiş qrafın əlaqə komponentlərini müəyyən edin.”
Giriş verilənləri
Qraf giriş faylında aşağıdakı kimi verilir: birinci sətir N və M ədədlərini ehtiva edir. Növbəti M sətirin hər biri kənarın təsvirini ehtiva edir - kənarın uclarının nömrələri olan 1 ilə N arasında olan iki tam ədəd.
Çıxış verilənləri
Yeganə sətirdə L ədədini çıxarın - verilmiş qrafın əlaqə komponentlərinin sayını.