Recherche:

Je confonds mes tentatives avec ton algorithme, oublie ça.

--
Jedaï

Non, le graphe résultant est bien fortement connexe, mais la minimalité ne marche pas (va falloir que je regarde de plus près l'algo). Par ailleurs le contre exemple donné par millie marcherait sur...

Je n'ai pas vérifié en détail l'implémentation, mais a priori vu ta description tu n'ajoute jamais plus d'arêtes que max(N / in = 0 , N / out = 0) donc la minimalité va de soi. Pour la correction,...

Ceux qui l'ont essayé ont dû pouvoir constater que la solution ci-dessus était parfaitement inutilisable sur des graphes de taille raisonnable. Nous pouvons néanmoins examiner la structure du...

Pour commencer par une solution de référence, exploration exhaustive des solutions :

import Data.Graph
import qualified Data.Set as S
import Data.Array
import Data.List
import Control.Arrow...