Dzień dobry
Mam problem z wymyśleniem wystarczająco szybkiego programu do policzenia spójnych składowych grafu, tyle, że na bieżąco są usuwane wyznaczone drogi. To mniej więcej coś takiego:
n-liczba miast m-liczba połączeń między nimi
Wejście->
n m
1 połączenie-> a b
2 połączenie-> c d
...
m-te ...
potem podajemy ilość modyfikacji (q) :
q
->modyfikacje->
np. 2 1

Wyjście->
gdy usuniemy 2 połączenie to będą 3 spójne składowe (a+b, c, d)
natomiast gdy usuniemy 1 połączenie to, w tym przypadku też, będą 3 spójne składowe (a, b, c+d)

Niestety to co udało mi się dotąd napisać jest dużo za wolne.
Byłbym wdzięczny za wszelką pomoc.

Zapomniałem wcześniej dodać, że BFS jak i DFS są za wolne.