[Algorithmie] Les chans IRC

[b0fh]

PS: il faut évidemment minimiser le nombre de chans.

Le format de sortie n'est pas précisé, mais une ligne par chan avec la liste des pseudos membres, ça me parait raisonnable !

Deuxième détail: en pratique, on ne ferait pas de chans de deux personnes, on dirait qu'ils causent simplement en privé, mais pour ce problème, considérons les privés comme des petits chans. Ou autrement dit, on cherche a minimiser le nombre total de chans + de privés.

Un exemple d'exécution:

Input:

Code :

1 2 3 4
1 2
1 3

Signifie que 1 et 2 ne s'aiment pas, et que 1 et 3 ne s'aiment pas, et la solution est:

Code :

1 4
2 3 4

soit 2 chans; on voit qu'en effet, 1 et 2 ne sont jamais dans le même chan, 1 et 3 ne sont jamais dans le même chan, et toutes les autres paires possibles [(1,4), (2,3), (2,4), (3,4)] existent dans au moins un chan.