Desi suna complicat, "umplerea unei gauri" necesita doar $O(N)$ timp pentru cautarea nodurile {$AB$}, {$CD$}, si incrucisare. Avand in vedere ca sunt maxim $N$ gauri la inceput, algoritmul necesita $O(N^2^)$ ca timp de executie.

Mai sus am folosit o afirmatie fara a o demonstra. Demonstratia e relativ intuitiva. Daca nu o descoperiti singuri, puteti sa intrebati pe "forum":http://forum.infoarena.ro/.

Mai sus am folosit o afirmatie fara a o demonstra. Demonstratia e relativ intuitiva. Daca nu o descoperiti singuri, puteti sa intrebati pe "forum":http://infoarena.ro/forum.

Problema luata in discutie este propusa pe lista "sgu":http://acm.sgu.ru/, nr. "122":http://acm.sgu.ru/problem.php?contest=0&problem=122, unde exista si evaluator online. Atentie la implementare! Citirea si scrierea folosind functii standard pot iesi din timp!