Qrafiklər üçün çox yayılmış bir üsul...#1977
Vitaliy Goldstein Qış Məktəbində qraf, ağ, qara və boz zirvələr, eləcə də dərinlik üzrə ilk axtarış (DFS) metodu ilə bir çox qraf məsələlərinin həlli barədə danışdı. Sonda isə proqramçıların çətin həyatı barədə danışmağa başlayıb, buna görə də hamıya 2011-ci ildə Xarkovda keçirilən Qış Məktəbində bu üsulla həll edilə biləcək daha bir tapşırıq verməyi unutdu. Təbii ki, Vitaliy bunu unuda bilməzdi və bizdən bu məsələni hamıya təklif etməyimizi xahiş etdi, çünki əsl usta məruzəçi kimi o, auditoriya ilə ünsiyyət zamanı, hətta bu ünsiyyət distant baş versə belə, heç bir, hətta sadə bir tapşırıq vermək fürsətini qaçırmamalıdır.
Beləliklə, budur, dərinlik üzrə ilk axtarış üsulu ilə həll edilə biləcək başqa bir sadə tapşırıq: "Sizə zirvəsi və təpəsi olan bir istiqamətsiz qraf verilir (1 \leq N \leq 20000, 0 \leq M \leq 200000). Qrafda döngələr və çoxlu təpələr yoxdur. Verilmiş qrafın əlaqəli komponentlərini müəyyən edin."
Qraf aşağıdakı kimi verilir: ilk sətirdə və ədədləri verilir. Sonrakı sətirin hər birində -dən -ə qədər olan iki tam ədəd — təpənin ucları qeyd olunub.
Yeganə sətirdə ədədini — verilmiş qrafın əlaqəli komponentlərinin sayını çap edin.
Nümunə 1