Runda 0 [Hard] - Niebezpieczne ścieżki

15.11.2010 - Damian Rusak
TrudnośćTrudność

Zadanie tygodnia

Runda 0; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 128MB


 

Niebezpieczne ścieżki

Jest burzliwa jesień na dalekiej prowincji. Baytard, syn lokalnego bankiera i znany awanturnik kupił właśnie nowy samochód wyścigowy. Zamierza jeździć nim po okolicznych miastach. Lokalne miejscowości połączone są siecią dróg. Drogi są dwukierunkowe. Baytard gardzi jeżdżeniem po bezpiecznych ulicach. Pragnie podróżować jedynie niebezpiecznymi ścieżkami. Jak one wyglądają? Otóż Baytard stwierdził, że najwięcej emocji sprawi mu podróż po drogach, na których wypadek byłby naprawdę spektakularny. Powiemy, że droga między dwoma miastami jest niebezpieczna jeśli wypadek na niej (czyli zablokowanie tej drogi) sprawiłby, że po sieci lokalnych dróg nie dałoby się przejechać (przez pośrednie miejscowości) pomiędzy parą miast, połączonych zablokowaną drogą.

Niebezpieczna ścieżka to ścieżka prosta (bez powtarzających się krawędzi), która składa się wyłącznie z niebezpiecznych dróg. Ponadto Baytard, nie chcąc być oskarżonym o tchórzostwo, chce wybrać taką ścieżkę, której nie dałoby się przedłużyć w żadną ze stron o kolejną niebezpieczną drogę. Na ile sposobów może wybrać taką niebezpieczną ścieżkę?

Wejście:

Pierwsza linia wejścia zawiera dwie liczby $ n $ i $ m $, oznaczające kolejno liczbę miast i liczbę dwukierunkowych dróg między nimi ($ 1 \leq n \leq 500000 $, $ 1 \leq m \leq 1000000 $). W kolejnych $ m $ liniach znajdują się pary liczb naturalnych $ a $ i $ b $ oznaczające, że miasta o numerach $ a $ i $ b $ są połączone drogą. Żadna para nie pojawi się na wejściu więcej niż raz.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę całkowitą - liczbę nieprzedłużalnych niebezpiecznych ścieżek. 

Przykład 1:

Wejście:

6 6
6 5
4 5
2 6
1 5
3 4
6 3

Wyjście:

2

Przykład 2:

Wejście:

4 3
1 2
1 3
1 4

Wyjście:

3

Na poniższych rysunku na czerwono są zaznaczone nieprzedłużalne niebezpieczne ścieżki dla obu przykładów (dla pierwszego 1-5 oraz 2-6, dla drugiego 2-1-3, 2-1-4, 3-1-4):

 

PozycjaImię i nazwiskoWynikCzas
1Przemek Komosa10132:40:15
2Szymon Stankiewicz10133:56:48
3Adam Czapliński10157:00:02
4Przemysław Derengowski10185:36:43
5Jakub Sygnowski10249:40:39
6Wojciech Żółtowski10612:26:32
7Witold Długosz102775:48:15
8Bartek Dudek2159:41:03
9Michał Kiełbowicz1148:16:54
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com