Runda 3: Bombowanie
24.06.2009
Dla Bajtocji nastały złe czasy. Rozliczne grupy terrorystyczne sieją chaos, zamęt i zniszczenie. Jedna z nich planuje właśnie przeprowadzenie zamachu bombowego gdzieś w kraju. Aby zamach odniósł zamierzony skutek, bomba musi zostać umieszczona na takim skrzyżowaniu ulic, żeby po detonacji, która zniszczy skrzyżowanie, przestała istnieć możliwość przejazdu między przynajmniej jedną parą skrzyżowań (inaczej mieszkańcy mogliby w ogóle nie zauważyć, że atak miał miejsce). Pomóż terrorystom (uwaga: to jest tylko zadanie, nie próbuj robić tego naprawdę)! Dla danej mapy połączeń drogowych w Bajtocji wyznacz skrzyżowania, na których mogą oni chcieć umieścić bombę. WejścieNa wejściu w pierwszej linii dane są liczby n, m (1 ≤ n ≤ 100 000; 1 ≤ m ≤ 1 000 000) oznaczające odpowiednio ilość skrzyżowań w Bajtocji oraz ilość dróg je łączących. Następnie danych jest m wierszy, z których każdy zawiera dwie liczby a, b (1 ≤ a, b ≤ n) oznaczające, że istnieje droga łącząca skrzyżowania o numerach a oraz b. WyjścieNależy wypisać ilość skrzyżowań, które mogą interesować terrorystów oraz ich numery w porządku rosnącym. Przykład
Dla danych wejściowych 15 17 poprawną odpowiedzią jest 3 kod: BOMBING, limity: 5 s, 32 MB |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com