h3. (problema usoara, clasa a 10-a)

Putem considera cele $N$ animale ca fiind noduri ale unui graf neorientat si o relatie de forma $i j$ ca fiind muchie intre nodurile $i$ si {$j$}. Problema cere determinarea numarului de triunghiuri in graful astfel construit ( numarul de triplete de noduri astfel incat intre oricare doua noduri din triplet exista muchie ). O solutie imediata are complexitatea {$O(N^3^)$}, prin generarea tuturor tripletelor. O solutie mai buna se bazeaza pe urmatorul rationament: pentru fiecare muchie din graf $a b$ trebuie sa vedem cate noduri adiacente cu $a$ si $b$ exista in graf ( adica cate triunghiuri care contin nodurile $a$ si $b$ se pot forma ). Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a nodurilor $a$ si $b$ si adunarea la numarul total de solutii a numarului de noduri comune. Acest algoritm are complexitatea {$O(M * N)$}, pentru ca parcurgerea unei liste de adiacenta se realizeaza in $O(N)$. Algoritmul de mai sus poate fi optimizat prin tinerea pe grupuri de biti a listei de adiacenta. Astfel, pentru orice nod {$i$}, primii $B$ biti din lista lui de adiacenta vor reprezenta legaturile cu primele $B$ noduri din cele {$N$} ( bit 1 pentru legatura si 0 altfel ), urmatorii $B$ biti legaturile cu nodurile $B+1...2*B$, etc. Pentru a vedea cate noduri adiacente comune exista intra $a$ si $b$ este suficient sa facem o operatie AND pe biti intre grupurile corespunzatoare de biti si sa aflam cati biti de 1 contine acest numar.

h2. Pachete