# ================================================
#  Sujet 1.
# ================================================

# Definitions des types
Sommet = int
Graphe  = dict[Sommet, Sommet]

# Graphes exemples
grapheSansCycle ={
    1: [2],
    2: [1, 3, 4],
    3: [2, 5],
    4: [2],
    5: [3]
}

grapheAvecCycle ={
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2, 5],
    5: [2, 4]
}

# Depth-First Search
def DFS(g: Graphe, s: Sommet) -> None:

    def etapeDFS(g: Graphe, s: Sommet, visites: list[Sommet]) -> None:
        visites.append(s)
        for voisin in g[s]:
            if voisin not in visites:
                etapeDFS(g, voisin, visites)

    stepDFS(g, s, [])


# Cycle detection
cycle = False # Define a global variable cycle

def existeCycle(g):
    global cycle
    cycle = False

    def etapeDFS2(g: Graphe, s: Sommet, \
                    prec: Sommet, visites: list[Vertex]) -> None:
        global cycle

        #
        # Compléter ici
        #
    #
    # Et un peu aussi ici
    #