*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, acesta 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 iar din momentul acela nu vor mai exista mutari, ganditi-va de cate ori poate fi mutat un nod pana sa faca parte din lista finala).

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, acesta 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 mutat un nod pana sa faca parte din lista finala).

*Solutia 2*