https://pl.spoj.com/problems/BIPART
Skrócony opis problemu:
Dla danego grafu nieskierowanego bez pętli należy sprawdzić czy da się pokolorować jego wierzchołki 2 kolorami (a więc nadać każdemu wierzchołkowi 1 z 2 kolorów tak, by każde 2 sąsiednie wierzchołki miały inne kolory).
Rozwiązanie naiwne:
Możemy sprawdzić wszystkie kombinacje pokolorowań i dla każdego sprawdzać czy warunek sąsiadów o przeciwnych kolorach jest spełniony. Można to łatwo zrobić generując kolejne ciągi binarne - 1 oznaczałaby jeden kolor, a 0 drugi (np. dla $n=3$: 000, 001, 010, 011, 100, 101, 110, 111).
Złożoność: $O(2^n \cdot (m+n))$, jako że ciągów takich jest dokładnie $2^n$, a dla każdego musielibyśmy sprawdzić czy każdy z wierzchołków spełnia warunek z zadania, a więc musielibyśmy sprawdzić także wszystkie krawędzie w grafie. Jeśli kolejne kody będziemy generować w systemie binarnym, to złożoność będzie większa - $O(2^n \cdot (m+n) \cdot n)$, gdyż zamiana kodu na następny będzie liniowa względem liczby wierzchołków. Jeśli jednak użyjemy kodu Graya, to będziemy mogli zrobić to w czasie stałym, jako że kolejne wyrazy ciągu w kodzie Graya różnią się tylko na 1 bicie.
Złożoność: $O(2^n \cdot (m+n))$, jako że ciągów takich jest dokładnie $2^n$, a dla każdego musielibyśmy sprawdzić czy każdy z wierzchołków spełnia warunek z zadania, a więc musielibyśmy sprawdzić także wszystkie krawędzie w grafie. Jeśli kolejne kody będziemy generować w systemie binarnym, to złożoność będzie większa - $O(2^n \cdot (m+n) \cdot n)$, gdyż zamiana kodu na następny będzie liniowa względem liczby wierzchołków. Jeśli jednak użyjemy kodu Graya, to będziemy mogli zrobić to w czasie stałym, jako że kolejne wyrazy ciągu w kodzie Graya różnią się tylko na 1 bicie.
Rozwiązanie sprytniejsze:
Przyjmijmy, że mamy niepokolorowany graf i zaczynamy od dowolnego wierzchołka X. Obojętne jest na jaki kolor go pomalujemy. Co dalej? No najłatwiej pokolorować jego sąsiadów na przeciwny kolor. No dobra, a potem? A potem bierzemy dowolnego sąsiada X i kolorujemy jego sąsiadów na kolor X. Następnie bierzemy kolejnego sąsiada X i kolorujemy i jego sąsiadów na kolor X. Po wyczerpaniu sąsiadów X bierzemy sąsiadów pierwszego sąsiada X. I tak dalej aż skończy nam się graf, a raczej spójna składowa. Następnie sprawdzamy czy są jeszcze jakieś spójne składowe i dla każdej z nich powtarzamy te operacje. Kiedy nie da się pokolorować grafu? Ano wtedy kiedy chcemy pokolorować wierzchołek na jakiś kolor, ale on już jest pokolorowany i to na inny kolor. Jeśli bowiem chcemy pokolorować wierzchołek, a on ma już przypisany ten kolor to nie ma problemu.
Ten względnie prosty algorytm nazywa się po prostu BFS (Breadth First Search - wyszukiwanie wszerz). Zaczynamy od jakiegoś wierzchołka i dodajemy jego sąsiadów do kolejki, a następnie ich sąsiadów itd.
Złożoność: $O(t \cdot (n+m))$, jako że mamy $t$ testów - każdy z 1 grafem, a dla każdego grafu BFS wykonuje $n+m$ operacji (bo przechodzimy wszystkie wierzchołki i krawędzie).
Algorytm:
vector<int> graph[1000009];
int color[1000009]; // kolory to 1 lub -1; 0 oznacza, że wierzchołek nie był kolorowany
bool bfs(int n)
{
queue<int> q; // kolejka wierzchołków
for(int i = 1, v; i <= n; ++i) // by nie przegapić żadnej spójnej składowej
{
if(!color[i]) // jeśli wierzchołek należy do pokolorowanej składowej to go pomijamy
q.push(i);
while(!q.empty()) // dopóki są niepokolorowane wierzchołki
{
v = q.front(); q.pop();
if(!color[v]) // jeśli wierzchołek nie był pokolorowany to go malujemy na arbitralny kolor
color[v] = 1;
for(int j = 0; j < graph[v].size(); ++j) // dla każdego sąsiada wierzchołka
if(color[graph[v][j]] == color[v]) // jeśli sąsiedzi mają taki sam kolor to zwracamy błąd
return 0;
else if(!color[graph[v][j]]) // jeśli niepokolorowaliśmy jeszcze tego sąsiada
color[graph[v][j]] = -color[v], // to kolorujemy go na przeciwny kolor niż v
q.push(graph[v][j]);
}
}
return 1;
}
int main()
{
int t, n, m, a, b;
get(n, m);
while(m--)
get(a, b),
graph[a].push_back(b),
graph[b].push_back(a);
puts(bfs(n) ? "TAK" : "NIE");
}
Rozwiązanie sprytniejsze nr 2:
Autorem tego rozwiązania jest Robert Kamiński.
A co gdybyśmy byli zachłanni i nie wczytywali najpierw całego grafu, tylko dla każdej kolejnej krawędzi wykonywali obliczenia? Załóżmy sobie taki algorytm. Wczytujemy krawędź. Jeśli mamy 1 z wierzchołków w grafie to przyznajemy drugiemu przeciwny kolor. Jeśli nie mamy żadnego, to przyznajemy im dowolne kolory. Jeśli natomiast mamy oba to sprawdzamy czy mają różne kolory - jeśli nie, to już wiadomo, że po wczytaniu reszty grafy wypiszemy "NIE". Wygląda poprawnie? Otóż tylko na pierwszy rzut oka. Błąd znajduje się przy losowym wybieraniu kolorów w przypadku, gdy nie mamy żadnego z wierzchołków w grafie. Może się bowiem stać, że utworzymy sobie 2 dobrze pomalowane składowe, ale potem dodamy krawędź, która je łączy, a oba incydentne do niej (leżące na niej) wierzchołki mają ten sam kolor. Moglibyśmy wtedy zamienić wszystkie kolory jednej składowej, ale taka sytuacja mogłaby zdarzać się często i psułaby nam tym samym złożoność.
A może da się jednak to jakoś prosto naprawić? Otóż tak. Co wtedy w przypadku gdy nie mamy jeszcze żadnego z wierzchołków w grafie? Nic - nadal arbitralnie wybieramy mu 1 z kolorów. Musimy jednak wtedy obsłużyć lepiej sytuację, kiedy mamy oba wierzchołki w grafie. Musimy po pierwsze sprawdzić czy są w tej samej składowej. Jeśli tak to sprawdzamy ich kolor - jeśli są różnych kolorów to wszystko jest ok - jeśli takich samych to już wiemy, że wypiszemy "NIE" po wczytaniu reszty krawędzi. Jeśli natomiast są w różnych składowych to musimy jakoś szybko przekolorować jedną z nich na przeciwne kolory. Jak to zrobić? Mapowaniem!
Przyjmijmy sobie, że wszystkie ujemne liczby są 1 kolorem, a dodatnie 2. Pierwszą składową kolorujemy liczbami 1 i -1. Jeśli pojawi się krawędź, której oba wierzchołki są poza 1 składową, to inkrementujemy licznik i kolory w tej składowej będziemy oznaczać przez 2 i -2. I tak dalej. Łatwo będzie sprawdzić wtedy czy 2 wierzchołki są z jednej składowej - wystarczy porównać wartości bezwzględne ich kolorów. A co zrobić jak 2 nowe wierzchołki są w różnych składowych? Wystarczy zmapować jedną składową na drugą. Potrzebujemy do tego jedynie tablicy, w której będziemy trzymali liczby reprezentujące składowe. A więc jeśli wierzchołki nowej krawędzi są w różnych składowych, to ustawiamy wartość w naszej tablicy z jednej składowej na drugą.
Musimy pamiętać tylko, żeby sprawdzać numer składowej w pętli. Może się bowiem zdarzyć, że zmapujemy składową 2 na 1, nasŧępnie 3 na 2, a potem 4 na 3. Nie możemy przy ostatnim mapowaniu sprawdzić jedynie wartości w tablicy dla 3, gdyż ta będzie miała zapisaną składową 2. Musimy również sprawdzić tablicę dla składowej 2. Oto przykład grafu, dla którego jedno sprawdzenie tablicy składowych nie wystarczy:
8 8 1 2 4 3 5 6 7 8 1 4 5 7 2 5 3 8
A oto jak wygląda:
Załóżmy, że jesteśmy przed dodaniem ostatniej, przerywanej krawędzi. Mamy takie oto wartości w tablicy skladowe: skladowe[] = {-2 -> -1, 2 -> 1, 4 -> -3, -4 -> 3, 3 -> 1, -3 -> -1}. Teraz chcemy połączyć wierzchołki o kolorach -4 i 2. Sprawdzamy, że 2 jest w składowej 1, a -4... w składowej 3. Gdybyśmy na tym poprzestali, to wyszłoby na to, że -4 i 2 są w różnych składowych a nie są! Musimy sprawdzić jeszcze czy 3 nie jest w jakiejś innej składowej. No i okazuje się, że jest - w składowej 1. Skoro oba wierzchołki są w tej samej składowej, to porównujemy ich znaki. Niestety mają takie same znaki: 1 i 1, więc 2 sąsiadów będzie koło siebie z tym samym kolorem. Zapamiętujemy to więc, żeby niepotrzebnie nie wykonywać już kolorowania następnych wierzchołków i kończymy wywołanie funkcji.
Złożoność: $O(t \cdot m)$, gdyż dla każdego testu przechodzimy jedynie wszystkie krawędzie, a dla każdej z nich sprawdzamy w czasie stałym w jaki ma kolor. Pewnie pomyślisz -"Chwila, chwila, przecież mamy pętlę w funkcji kolorowania! Ona niby wykonuje się w czasie stałym‽". Otóż wg mnie tak. Wydaje mi się, że będą maksymalnie 2 przebiegi pętli. Dlaczego? Gdyż zawsze zapisujemy w tablicy skladowe "najstarszą" składową (czyli tą która była wcześniej). Tak więc sprawdzamy składową danego wierzchołka, a jeśli jest już on w jakiejś składowej to sprawdzamy tamtą składową, a ona będzie już miała dobrą wartość. Jeśli ktoś potrafi podać przykład, dla którego pętla for z 2 obiegami zwróci złą odpowiedź, to zachęcam do podzielenia się w komentarzu.
Algorytm:
const int N=1000000;
int color[N + 1], tmp[2*N + 1], *skladowe = tmp + N, nr, n, m, x, y; // tmp to tymczasowa tablica która po to, byśmy mogli stworzyć wskaźnik na jej środek (w komórce N), by odwoływać się niejako do ujemnych komórek tej tablicy
bool colorize(int a, int b)
{
if(color[a] && color[b]) // jeżeli oba wierzchołki wystąpiły już w grafie
{
int c1 = color[a], c2 = color[b];
while(skladowe[c1]) // dopóki wierzcholek jest w jakiejś zmapowanej składowej
c1 = skladowe[c1]; // aktualizuj kolor wierzchołka
while(skladowe[c2])
c2 = skladowe[c2];
if(abs(c1) == abs(c2)) // jeśli kolory należą do tej samej składowej
return c1 == -c2; // sprawdź czy sąsiedzi mają różne kolory
skladowe[c2] = -c1; skladowe[-c2] = c1; // aktualizuj składowe wierzchołków
}
else if(color[a]) // jeżeli wierzchołek a wystąpił już w grafie
color[b] = -color[a]; // nadajemy wierzchołkowi b przeciwny kolor
else if(color[b])
color[a] = -color[b];
else // jeżeli żaden wierzchołek nie wystąpił jeszcze w grafie
color[a] = ++nr, // nowa składowa, arbitralny kolor (dodatni)
color[b] = -color[a]; // przeciwny kolor
return 1;
}
int main()
{
bool ok = 1;
get(n, m);
while(m--)
get(x, y),
ok = ok && colorize(x, y);
puts(ok ? "TAK" : "NIE");
}
Brak komentarzy:
Prześlij komentarz