==include(page="onis-2015/solutii-runda-1/meciul")==

Aceasta problema se rezuma la urmatorul lucru: Avem un graf bipartit si, primind query-uri de adaugare de muchii, vrem sa stim daca isi pastreaza natura de graf bipartit si, daca da, sa adaugam muchia.
 
*Solutia 1*
 
La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi <tex>O(M + N*logN)</tex>. Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste, ganditi-va de cate ori poate fi rmutat un nod pana sa faca parte din lista finala).
 
*Solutia 2*
 
Distingem 3 cazuri:
 
* Apare o muchie intre doua noduri izolate X si Y. Punem muchia. Utilizam o pereche de culori care nu a mai fost folosita pana acum (a,b). Il coloram X cu a si pe Y cu b.
* Apare o muchie intre un nod izolat si un nod neizolat. Punem muchia. Nodul neizolat este deja colorat cu o culoare. Coloram nodul izolat cu perechea acestei culori.
* Apare o muchie intre doua noduri neizolate. Daca culorile lor coincid, afisam NO, altfel punem muchia. Sa zicem ca nodurile sunt X si Y iar culoarea lui X este a din perechea de culori (a,b) iar culoarea lui Y este c din perechea de culori (c,d). Vrem sa exprimam ca, de acum in colo, a este echivalent cu d iar b este echivalent cu c. Pentru aceasta putem folosi 'paduri de multimi disjuncte':http://www.infoarena.ro/problema/disjoint.
 
Complexitatea este <tex>O(N + M)</tex>.
 
 

==include(page="onis-2015/solutii-runda-1/perechile")==
==include(page="onis-2015/solutii-runda-1/pinball")==