E13 - Plan de métro

Le problème

Plan de métro

Proposition 1

🐍 Script Python

from collections import deque

dictionnaire = dict()

identifiant_station = int(input())
nombre_connexions = int(input())

def ajout_sommet(sommet):
    """
    Permet d'ajotuer un sommet au dictionnaire
    >>> ajout_sommet(4)
    None
    >>> ajout_sommet(5)
    None
    """
    if sommet in dictionnaire:
        return
    else:
        dictionnaire[sommet] = []

def ajout_flèche(sommet_1, sommet_2):
    """
    Permet d'ajouter un arc orienté de `sommet_1` à `sommet_2`
    >>> ajout_flèche(9, 7)
    None
    >>> ajout_flèche(8, 4)
    None
    """
    ajout_sommet(sommet_1)
    ajout_sommet(sommet_2)
    dictionnaire[sommet_1].append(sommet_2)

def parcours_largeur(sommet_départ):
    """
    Permet de renvoyer une liste avec le parcours en largeur à partir de `sommet_départ`
    """
    file = deque()
    défile = file.popleft
    enfile = file.append
    déjà_parcouru = list()
    enfile(sommet_départ)
    déjà_parcouru.append(sommet_départ)
    while len(file) != 0:
        sommet = défile()
        for voisin in dictionnaire[sommet]:
            if voisin not in déjà_parcouru:
                enfile(voisin)
                déjà_parcouru.append(voisin)
    return déjà_parcouru  

for _ in range(nombre_connexions):
    sommet_1, sommet_2 = map(int, input().split(" "))
    ajout_flèche(sommet_1, sommet_2)

liste_parcours_largeur = parcours_largeur(identifiant_station)
sommet_le_plus_éloigné = liste_parcours_largeur[len(liste_parcours_largeur)-1]

def donne_liste_chemin(sommet_début, sommet_fin):
    """
    Permet de donner la liste des chemins partant de `sommet_début` et
    `sommet_fin`
    """
    liste_parcours_largeur.reverse()
    ensemble_chemin = {sommet_fin}
    dernier_sommet = sommet_fin
    for sommet in liste_parcours_largeur:
        if dernier_sommet in dictionnaire[sommet]:
            dernier_sommet  = sommet
            ensemble_chemin.add(sommet)
    return ensemble_chemin

longueur_chemin = len(donne_liste_chemin(identifiant_station, sommet_le_plus_éloigné)) -2
if longueur_chemin == 3 and identifiant_station != 3:
    print(dictionnaire, liste_parcours_largeur, sommet_le_plus_éloigné, identifiant_station,)
else:
    print(longueur_chemin)

• Il y a un beau travail ici !!!
  • C'est un très bon début ; bravo même s'il ne fonctionne pas.
  • Étudie le corrigé pour voir le détail qui manque.

Corrigé du professeur

🐍 Script Python

"""
author : Franck CHAMBON
problem: https://prologin.org/train/2003/semifinal/plan_de_metro
"""

def main():
    depart = int(input())

    nb_liens = int(input())
    # construction du graphe
    graphe = dict()
    for _ in range(nb_liens):
        station_a, station_b = map(int, input().split())
        for _ in range(2):
            if station_x not in graphe:
                graphe[station_x] = [station_y]
            else:
                graphe[station_x].append(station_y)
            station_a, station_b = station_b, station_a

    # parcours en largeur en partant de départ,
    # avec calcul de la distance maximale atteinte
    courant = {depart}
    vus = {depart}
    distance = 0
    while courant != set():
        suivant = set()
        for station_a in courant:
            for station_b in graphe[station_a]:
                if station_b not in vus:
                    suivant.add(station_b)
                    vus.add(station_b)
        courant = suivant
        distance += 1
    print(distance - 2)
    # on enlève 2.
    # 1 pour le dernier ajout de 1 à vide,
    # 1 autre pour le nombre de station intermédiaire au lieu de la distance.

main()

• Il suffit de construire le graphe, et d'en faire un parcours en largeur depuis départ.

• Il faut penser aussi à créer de petits fichiers tests avec une boucle en fin de course. Comme le suivant, où la sortie attendue est 0.

📋 Texte

1
3
1 2
2 3
1 3

Exercice : réécrire ce code avec un style POO.