Thread: [MIS] Rozwiązanie

Mógłby ktoś opisać optymalne?
Algorytm jest dość prosty:
- dopóki w grafie istnieje wierzchołek o stopniu <d, usuń go (bo taki wierzchołek nie może należeć do rozwiązania)
- jeśli każdy wierzchołek ma stopień >=d to graf spełnia warunek (1)
- rozwiązanie to największa spójna składowa pozostałego grafu -- spełniamy w ten sposób warunek (2)
Pozostaje kwestia efektywnej implementacji.
Ja robię to tak, że dla każdego wierzchołka pamiętam jaki ma stopień. Po kolei dla każdego wierzchołka jeśli jest nieodwiedzony i ma stopień <d odpalam dfsa. W dfsie każdemu sąsiadowi zmniejszam stopień o 1 (bo usuwam aktualnie przetwarzany wierzchołek) i jeśli w wyniku tego stopień spadnie poniżej d to tam idę dalej dfsem. Nieodwiedzone wierzchołki grafu tworzą graf spełniający warunek (1).
Hmmm... Algorytm był właśnie taki w moim zamyśle, a dawał wiele złych odpowiedzi. Czy ktoś mógłby poszukać w nim błędu:

http://paste.ubuntu.com/12638670/
Jak idziesz pętlą po V[a] i wywołasz removeEdge(a,b) to usuwasz też element z V[a] i iterator głupieje (prawdopodobnie wskazuje jakiś inny element).
Swoją drogą usuwanie elementu z vectora jest liniowe i raczej nie powinno przejść czasowo w tym zadaniu (wyobraź sobie graf-gwiazdkę, wtedy z vectora środkowego elementu usuwasz O(n) razy, każdy w O(n)).
Hmmm...

U mnie `class vertex : public set<int>`, a set::erase jest O(log n): http://www.cplusplus.com/reference/set/set/erase/

A w funkcji graph_t::removeVertex ja tak naprawdę nie usuwam samego wierzchołka, tylko wszystkie krawędzie wychodzące z niego (wierzchołek staje się izolowany), więc wskaźnik do następnego elementu pozostaje w zbiorze zachowany (zbiór przecież jest zwykle realizowany jako lista)
Robisz w kodzie coś mniej więcej takiego:
for (vertex::iterator it = V[a].begin(); it != V[a].end(); ++it) {
V[a].erase(*it); // w funkcji
cośtam(*it);
}

Przy wywołaniu cośtam, a także przy ++it iterator jest już popsuty i to co się wtedy dzieje nie jest określone przez standard.

Sprawdź czy taka zmiana coś naprawi:
for (vertex::iterator it = V[a].begin(); it != V[a].end();) {
int b = *it;
it++;
V[a].erase(b); // w funkcji
cośtam(b);
}