Yanma və əlaqə komponentləri#4371
Bir dəfə siz qrafın necə yandığını müşahidə etdiniz - bu çox maraqlı bir prosesdir. Əvvəlcə qraf yanır, amma əlaqəli qalır, sonra bir anda o, ayrı-ayrı əlaqəli hissələrə parçalanmağa başlayır və bir müddət sonra bu ayrı-ayrı hissələr tamamilə yanır və yox olur.
Qrafın yanmasını izləmək sizə o qədər xoş gəldi ki, onu kompüterinizdə modelləşdirməyə qərar verdiniz. Bunun üçün sizə belə bir sualın cavabını tapmaq lazımdır: Yanğından i saniyə sonra qrafda yanmamış zirvələrdən ibarət neçə əlaqə komponenti olacaq? Həmçinin, hər bir i üçün cavabı tapmaq lazımdır, 0-dan K-yə qədər, burada K - yanabilən son zirvənin yanma vaxtıdır.
Birinci sətirdə N, M və S (1 ≤ N, M ≤ 10^5, 1 ≤ S ≤ N) - zirvələrin sayı, kənarların sayı və yanğın başlanğıc zirvəsinin nömrəsi verilir. Sonra M sətir qrafın kənarlarını iki ədəd a və b (1 ≤ a, b ≤ N) ilə təsvir edir - növbəti kənarın ucları. Qraf çoxlu kənarlar və döngələr ehtiva edə bilər.
Birinci sətirdə K ədədini çıxarın - yanabilən son zirvənin yanma vaxtı. Fərz edin ki, S zirvəsi t=1 saniyə anında yanır və alov istənilən iki qonşu zirvə arasında bir saniyə ərzində yayılır. Növbəti sətirdə K+1 ədədini boşluqla çıxarın, burada i-ci ədəd i saniyə bitdikdən sonra ( 0 ≤ i ≤ K) hələ yanmamış zirvələrdən ibarət əlaqə komponentlərinin sayını göstərir.
İzah: Birinci nümunədə 0 saniyədə, yəni yanğından əvvəl, qraf əlaqəlidir - əlaqə komponentlərinin sayı 1-ə bərabərdir. 1-ci saniyənin sonunda 2 zirvəsi yanır və qraf iki əlaqə komponentinə parçalanır (5) və (1, 3, 4). 2-ci saniyədən sonra 5, 1 və 3 zirvələri yanır. Yalnız bir zirvə 4 qalır, o da əlaqə komponentini təşkil edir. 3-cü saniyədən sonra 4-cü zirvə yanır və əlaqə komponentləri yoxdur, çünki bütün zirvələr yanıb.
İkinci nümunədə 0 saniyədə qraf üç ayrı zirvədən ibarətdir - 3 əlaqə komponenti. Birinci zirvə yandıqda, o, 1-ci saniyədə yanır və iki əlaqə komponenti qalır. Daha heç bir zirvə yanmayacağı üçün axtarılan yanma vaxtı 1-ci saniyəyə bərabərdir.
Nümunə 1