Qrafın rənglənməsi#3163
Verilmiş qraf üçün optimal rəngləmə tapmağa çalışan bir proqram yazmalısınız. Rənglər qrafın düyünlərinə tətbiq olunur və yalnız iki rəng mövcuddur: qara və ağ. Qrafın rəngləməsi, qara düyünlərin sayını maksimuma çatdırırsa, optimal sayılır. Rəngləmə qaydasına əsasən, bir-birinə bitişik olan heç bir iki düyün eyni zamanda qara ola bilməz.
Şəkil 1: Üç qara düyünlü optimal qraf rəngləməsi
Qraf ( n \leq 100 ) nömrəli düyünlər çoxluğu və (n_1, n_2) (n_1 \neq n_2) tipli bitişik düyün cütləri ilə verilmiş təhlilsiz (istiqamətsiz) qraf şəklində təsvir olunur. Daxildə qraf verilir. Birinci sətirdə ədədi göstərilir. Hər bir qrafın təsviri ayrıca başlayır, ilk sətirdə və —düyünlərin və kənarların sayı verilir. Növbəti sətirin hər birində kənarları—aralarında boşluq olan iki düyün nömrəsi göstərilir.
Çıxışda, girişdəki hər bir qraf üçün iki sətr olmaqla sətir olmalıdır. Hər bir cüt sətirin birincisində qrafda qara rəng alacaq maksimum düyün sayı verilir. İkinci sətir isə, bu optimal rəngləmələrdən birinin mümkün bərpa olunmasını—qara düyünlərin nömrələrinin boşluqlarla ayrılmış siyahısını əks etdirməlidir.
Nümunə 1