Hippopotame (./41192) :
Pour la capture, je pense simplement qu'il ne faut pas détruire le morceau de graphe à partir duquel a été construit une chaîne : chaque chaîne n contient une référence vers ses 2 à 5 ancêtres, v et n, à partir desquels elle a été créée par fusion. Quand la chaîne est détruite par capture, on reparcourt ses ancêtres pour reconstituer les v. Il n'y a pas énormément de travail à faire, parce que les flèches ont été conservées en mémoire. C'est juste casse tête à implémenter.

Ah oui c'est faisable aussi si tu gardes l'historique, par contre c'est potentiellement plus coûteux. Tu as une idée de la différence entre O(aire) et O(périmètre) ? Si on évaluait juste une partie linéaire ça n'aurait pas d'importance (une destruction de n pierres n'arrive qu'après n constructions de pierres donc c'est amorti) mais là c'est pas vraiment le cas (surtout si tu autorises les suicides, une pierre construite sera détruite des tonnes de fois).