Ciao a tutti,
sto cercando di trovare un modo per contare il numero di cicli composti da M elementi in un grafo non diretto con complessità ottimale e veloce da scrivere
Qualcuno ha un idea?
( il problema è del 2008 delle oii, devo trovare il numero di cicli composti da 3 nodi)
Potresti mettere il link dell’esercizio?
Non sono riuscito a risolverlo neanch’io, 70/100 
In un grafo generico con N nodi il numero di cicli di lunghezza K può arrivare a \binom{N}{K} = \frac{N!}{K!(N-K)!} se il grafo è completo. Se volessimo contare i cicli di lunghezza 3 in maniera naive avremmo una complessità di \frac{N!}{3!(N-3)!} = \frac{N(N-1)(N-2)}{6} = \mathcal O(N^3), che con N \leq 10^5 non è assolutamente fattibile.
Le limitazioni del problema ci permettono però di fare di meglio. In particolare il numero di archi è relativamente piccolo, M \leq 2N-3 \lt 2\cdot 10^5. Possiamo iterare sugli archi e controllare per ognuno di questi se esiste un nodo che forma un ciclo da 3. Per farlo possiamo, per ogni arco (A,B), iterare tra tutti i vicini V_i di A e controllare se B è presente tra i vicini di V_i. Ogni volta che è presente in uno dei vicini incrementiamo un contatore C, e il risultato sarà \frac{C}{3}.
Questo algoritmo a una prima analisi è comunque \mathcal O(MN^2) e non sta nei tempi. Possiamo ottimizzare l’ultima fase, la ricerca di B in V_i mantenendo per ogni nodo un set o un vettore ordinato con tutti i vicini e portare quindi questa fase di ricerca a \mathcal O(logN).
Se invece di iterare sempre su A per ogni arco iteriamo sull’estremo che ha grado minore, la complessità si abbassa ancora a quello che dovrebbe essere \mathcal O((N+M)logN), che finalmente sta nei tempi.
Spero si capisca 
Dario
Spiegazione perfetta, grazie mille
Come fa la complessità ad abbassarsi fino a O((N+M)logN)?
Ci sarei arrivato di logica ad una soluzione (nel caso peggiore avremmo molti meno nodi da iterare) però da cosa è determinata in modo specifico quella complessità?
Grazie della risposta 
Intanto mi correggo, la complessità è ancora migliore.
Per ottenerla pensiamo al caso peggiore possibile per l’algoritmo, quando tutti i nodi hanno lo stesso grado K.
In questo caso avremo N nodi di grado K, per un totale di M=\frac{N\cdot K}{2} archi.
Possiamo scrivere la complessità dell’algoritmo in prima analisi come \mathcal O(MKlogK), perchè per ogni arco iteriamo su tutti i vicini di un estremo e cerchiamo ogni volta l’altro estremo in un set di grandezza K.
Sostituendo otteniamo \mathcal O(\frac{2M^2}{N}log\frac{2M}{N}), e ricordando che N-1 \leq M \leq 2N-3, possiamo dare dei limiti sul tempo d’esecuzione \tau, assumendo che sia una funzione monotona:
\mathcal O(\frac{2(N-1)^2}{N}log\frac{2(N-1)}{N}) \leq \tau \leq \mathcal O(\frac{2(2N-3)^2}{N}log\frac{2(2N-3)}{N})
Ma entrambe le complessità sono asintoticamente uguali, e risulta \tau = \mathcal O(N)
Fin.
Ammetto che mi sembra strano che venga fuori lineare, pensavo avesse un fattore log da qualche parte . Anyways, se qualcuno trova errori me lo faccia sapere, quando si tratta di matematica non sono certo un imoista.
Aggiungo una cosa:
data una coppia di array ordinati lunghi N e M, si può controllare quante e quali sono le loro intersezioni in \Theta(N+M), quindi possiamo alleggerire l’ipotesi O(MK\log K) con O(MK). Il resto rimane praticamente invariato.
EDIT:
Mea culpa, ci sbagliavamo. Il caso peggiore è la stella: dovremo ordinare tutti i vertici adiacenti al centro, poi per ogni arco fare ricerca binaria sul vertice con grado maggiore e quindi ottenere T(N) = O(N \log N) + O((N-1) \log (N-1) ) = O(N \log N)