< style="text-align: center">Sesja
na dół
Różne ścieżki
W pewnej miejscowości znajduje się olbrzymi park z dużą liczbą ławek położonych w różnych odległościach przy ścieżekach i ponumerowane są od 0 do n. Zapis “i j” oznacza, że z ławki o numerze i można dojść do ławki o numerze j, idąc po tej samej ścieżce. Ile różnych (niepołączonych) ścieżek znajduje się w parku?

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą m (m ≤ 10^6), oznaczającą liczbę wszystkich par i, j < 10^6 numerów ławek połączonych ze sobą tą samą ścieżką, rozdzielonych spacją oraz zakończonych znakiem nowej linii.

Wyjście:

Liczba całkowita będąca liczbą niepołączonych ścieżek, zakończona znakiem nowej linii.
 
Przykład
Wejście:
5
0 1
5 3
0 3
2 4
1 3
Wyjście:
2
Wskazówka:
DFS i spójne składowe.


Rozwiązanych zadań 0:

Powrót do zadań

engine by marwoj