A vrai dire, je ne construis pas vraiment le graphe, je déduis les voisins à partir de la grille.
Par contre, j'ai besoin de stocker un tableau des degrés.
Je me demande si je ne peux pas réutiliser le tableau de la grille et le modifier.
Mais je ne suis pas sûr que je gagne vraiment en temps de calcul.
Les sommets stockés dans la pile ne le sont qu'une seule fois car ils sont insérés seulement quand leur degré vaut exactement 3 et par la suite le degré sera inférieur à 3.
Sinon, pour les curieux, j'ai appris aujourd'hui que ce problème s'appelle k-core.
Plus précisément, le k-core d'un graphe est le plus grand sous-graphe H où tous les sommets ont au moins k sommets voisins à l'intérieur H.
Donc on cherche ici à trouver le nombre de sommets n'appartenant pas au 4-core.
[^] # Re: Jour 4
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 2.
A vrai dire, je ne construis pas vraiment le graphe, je déduis les voisins à partir de la grille.
Par contre, j'ai besoin de stocker un tableau des degrés.
Je me demande si je ne peux pas réutiliser le tableau de la grille et le modifier.
Mais je ne suis pas sûr que je gagne vraiment en temps de calcul.
Les sommets stockés dans la pile ne le sont qu'une seule fois car ils sont insérés seulement quand leur degré vaut exactement 3 et par la suite le degré sera inférieur à 3.
Sinon, pour les curieux, j'ai appris aujourd'hui que ce problème s'appelle k-core.
Plus précisément, le k-core d'un graphe est le plus grand sous-graphe H où tous les sommets ont au moins k sommets voisins à l'intérieur H.
Donc on cherche ici à trouver le nombre de sommets n'appartenant pas au 4-core.