Ciao a tutti, sono alle prese con un esercizio di un corso di base di Algoritmi, sono un po' di giorni che ci penso ma non riesco a trovare una soluzione. La traccia é:
Supponiamo di avere n carte di credito {1....n} tale che due o più carte possono essere associate allo stesso conto. Supponiamo inoltre di possedere una funzione test(i,j) che restituisce TRUE se le carte i e j sono associate allo stesso conto e FAlSE in caso contrario. Determinare un algoritmo che faccia uso della funzione test O(nlogn) volte e che determini se, tra le n carte, più della metà sono associate allo stesso conto.
Ho pensato che se costruissi un grafo con nodi {1...n} in cui vi é un arco tra i e j se test(i, j)=TRUE il problema si ridurrebbe allo studio delle componenti connesse di un grafo, di cui abbiamo fatto a lezione l'algoritmo bastato sulla ricerca DFS. Non sono riuscito però a trovare un algoritmo che costruisca questo grafo utilizzando la funzione test O(nlogn) volte, ne mi sono venute altre idee più intelligenti..