Mai trebuie mentionat ca complexitatea algoritmului este data de complexitatea descompunerii in cicluri, care se face in O(N). Ca sursa de referinta voi folosi sursa mea din Arhiva Monthly: http://pastebin.com/uKm4TvN2

h2. 'Petrecere2':problema/petrecere2
 
Aceasta a fost problema grea a setului. Ea a fost rezolvata corect doar de 8 concurenti. Cu toate astea, problema nu era atat de grea odata ce se faceau niste observatii cheie. Codarea solutiei trebuia facuta cat mai simplu posibil si aici, altfel puteau aparea buguri care sa compromita toata problema.
 
Pentru inceput, putem considera fiecare persoana un nod intr-un graf si fiecare relatie o muchie neorientata in graf. Daca tipul relatiei era 0, vom numi muchia muchie de tip 0, altfel muchia va fi de tip 1. Problema cere o colorare a grafului. Vom spune ca un nod are culoare alba daca persoana corespunzatoare lui vine la petrecere si neagra daca nu vine. In exemplu, nodurile 1 si 2 sunt albe si nodul 3 este negru.
 
Observatia cheie care rezolva problema este ca daca stiu culoarea unui nod x pot afla culoarea tuturor nodurilor din componenta conexa a lui x. Pentru asta sa analizam mai atent tipul muchiilor:
 
* O muchie de tip 0 dintre doua noduri x si y arata ca x si y au aceeasi culoare. Sa presupunem ca x este alb. Persoana X ar veni la petrecere numai daca toate persoanele cu care se afla in relatii de tip 0 ar veni. Implicit, persoana Y trebuie sa vina, deci culoarea lui Y este tot alb. Acum, daca x ar avea culoarea neagra, Y este obligat sa aiba culoarea neagra si el. Rationamentul este asemanator: Y vine la petrecere doar daca vine si X, cum X nu vine, nici Y nu vine.
* O muchie de tip 1 dintre doua noduri x si y arata ca x si y au culori diferite. Presupun si aici ca x e alb. Daca x vine la petrecere, y nu va veni (conform definitiei relatiei de tip 1). De asemenea, daca x nu vine, y trebuie sa vina ("Paftenie mai stie ca daca 2 prieteni de-ai sai se afla in relatia de dusmanie, trebuie neaparat sa il invite pe unul din ei altfel vor fi amandoi suparati.")
 
De aici se contureaza ideea algoritmului. Pornim dintr-un nod arbitrar, presupunem ca el are culoare alba. Apoi aflam toate nodurile din componenta conexa a nodului ales (se poate face prin parcurgeri precum BFS si DFS) si pentru fiecare nod y descoperit dintr-un nod x vom actualiza culoarea lui y in functie de culoarea lui x si tipul muchiei dintre x si y. Daca nodul ales arbitrar ar avea culoarea neagra, tot ce s-ar intampla ar fi ca nodurile albe din componenta conexa sa devina negre si nodurile negre sa devina albe. (Las tema de gandire pentru cititori demonstrarea acestei proprietati). Astfel, e nevoie sa parcurg graful doar pentru culoarea alba initiala, pentru culoarea neagra se poate afla prin contrast.
 
Mai departe, calculez pentru nodul ales arbitrar mai sus daca e mai bine sa-l colorez in alb sau negru. Evident, o colorare se considera buna cand aduce un numar maxim de noduri albe. Fie N = nr de noduri din componenta conexa curenta si white = numarul de noduri albe. Pentru o colorare pornind cu culoarea initiala alba, numarul de noduri albe va fi white. Daca am porni cu negru initial, numarul de noduri negre ar fi white si numarul de noduri albe ce mai ramane din cele N noduri ale componentei (N - white). Astfel, pentru o componenta conexa, la solutie se va adauga valoare max(white, N - white). Dupa aceea componenta conexa se elimina si algoritmul se reia.
 
Timpul de rulare al algoritmului este O(N + M). Practic, eliminarea unui nod se poate face in O(1) daca il marchez ca fiind vizitat, iar in timpul unei parcurgeri consider numai nodurile nevizitate. Ca sursa de referinta recomand sursa mea - parcurgerea grafului a fost facuta cu DFS pentru a scurta codul: http://pastebin.com/WVJL1tyr

h2. 'Petrecere2':problema/petrecere2