Qrafın istiqamətləndirilməsi#2800
düyünlü, -dən -ə qədər nömrələnmiş təyin olunmamış qraf verilib. Aşağıdakı tapşırıqları sırayla həll edən proqram yazın:
[a)] Qrafın əlaqəli komponentlərinin sayını tapın.
[b)] Silinməsi əlaqəli komponentlərin sayını artıran bütün kənarları tapıb çıxışa verin.
[c)] Qrafın bütün kənarlarını elə istiqamətləndirmək mümkün olub-olmadığını müəyyən edin ki, alınan istiqamətli qraf güclü əlaqəli olsun (istiqamətli qraf güclü əlaqəlidir, əgər istənilən düyündən istənilən digərinə kənarların istiqamətinə uyğun gedib çatmaq mümkün olarsa).
[d)] İstiqaməti elə verilə biləcək maksimum sayda kənarı tapın ki, alınan istiqamətli qraf güclü əlaqəli olsun və onları çıxışa verin.
[e)] Tapın ki, minimum neçə kənar əlavə etmək lazımdır ki, c) bəndinə cavab müsbət olsun və lazım olan kənarları verin.
Giriş faylında bir tam ədəd (1 \leq N \leq 100) və qrafın kənarlarının siyahısı – onların qurtaracaq düyünlərinin nömrələri verilir.
Proqramınız a)–e) bəndlərinə aid cavabları aşağıdakı formatda çıxışda verməlidir:
Birinci sətrdə a) bəndinin cavabını verin.
İkinci sətrdə b) bəndinə aid kənarların sayını, sonra isə növbəti sətrlərdə həmin kənarların siyahısını verin.
Növbəti sətrdə, əgər c) bəndinin şərtini ödəmək mümkün deyilsə, "NOT POSSIBLE" çap edin; əks halda "POSSIBLE" yazın.
Sonra, d) bəndinə aid qrafın güclü əlaqəli olmasını təmin edən istiqamətlənmiş maksimum sayda kənarların sayını və növbəti sətrlərdə onların başlanğıc və son düyünlərini verin.
e) bəndinə görə, başlanğıc qrafa neçə kənar əlavə edilməli olduğunu və həmin kənarların siyahısını çap edin.
Kənarlar düyünlərin nömrələri ilə verilir, d) bəndinə cavabda isə onların istiqaməti göstərilməlidir (əvvəl başlanğıc, sonra son düyün).
Əgər a) bəndinə cavab bir deyilsə, c) və d) bəndlərini həll edib çıxışda göstərməyin.
Bütün tapşırıqlara düzgün cavab verildiyi halda xal maksimum olur.
Nümunə 1