Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita _longest path decomposition_. Si, desigur, nu este rau daca stim ceva in plus. :)

Tehnica liniarizarii arborelui nu poate functiona, deoarece informatiile pe care le putem retine nu ne pot permite sa obtinem o complexitate mai buna.

Tehnica liniarizarii arborelui este inapta functionarii, deoarece informatiile pe care le putem retine nu permit obtinerea unei complexitati mai bune.

Insa, cu _longest path_decomposition_, tehnica ce necesita cunostine minime despre grafuri, vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos: