# -*- coding: utf-8 -*-
"""
Created on Wed Jan 25 00:03:48 2023

@author: dconduche

Exercices 5 et 6
"""

G = [[1, 3, 7], [2, 5], [3], [1], [0], [6, 7], [5, 1], [4]]

#### Exercice 5

## Q1
print("QUESTION 1")

G = [[1, 3, 7], [2, 5], [3], [1], [0], [6, 7], [5, 1], [4]]
n = len(G)
s = 0        # Toujours des variables, partout des variables

c = ['b'] * n
p = [-1] * n
# Le sommet de départ :
c[s] = 'g'

print('c =', c)
print('p =', p)


## Q4
print("QUESTION 2")


def visiter_sommet(u):
    c[u] = 'g'         # on colorie u en gris
    for a in G[u]:       # on parcourt les sommets voisins de u..
        if c[a] == 'b':  # ..blancs
            p[a] = u     # leur père est u
            visiter_sommet(a)
    c[u] = 'n'        # on a fini de visiter u (et les arêtes partant de u)

print(c, p)
visiter_sommet(0)
print(c, p)
## Q3
print("QUESTION 3")


def parcours_en_profondeur(G, s):
    n = len(G)
    c = ['b'] * n
    p = [-1] * n
    # Le sommet de départ :
    c[s] = 'g'
    
    def visiter_sommet(u):
        c[u] = 'g'         # on colorie u en gris
        for a in G[u]:       # on parcourt les sommets voisins de u..
            if c[a] == 'b':  # ..blancs
                p[a] = u     # leur père est u
                visiter_sommet(a)
        c[u] = 'n'        # on a fini de visiter u (et les arêtes partant de u)
    visiter_sommet(s)
    return p

print(parcours_en_profondeur(G, 0))

## Q7
print("QUESTION 7")
"""La coloration blanc -> gris assure que la fonction « visiter_sommet »
est appellée une fois et une seule sur chaque sommet, elle est donc appellée
exactement n=|S| fois. Dedans il y a au moins 2 affectations (c[u] à gris,
puis noir). Les boucles for dans leur ensemble parcourent chaque arête une fois
et une seule : il y a donc |A| passage dans les boucles for.

En conclusion, l'algorithme est de complexité O(|S|+|A|)
"""


#### Exercice 6
print("Exercice 6")
##Q1
p = parcours_en_profondeur(G, 0)

"""En console, on remonte
p = parcours_en_profondeur(G, 0)
p
p[5]
p[1]
donc le chemin vers 7 est 0 -> 1 -> 5 -> 7
"""

##Q2
print("QUESTION 2")
"""Sans boucle ni fonction"""
u = 7
# initialisation :
L = []
if p[u] != -1:
    L.append(u)
print(L)
"""avec un appel récursif"""
L = []

def cheminRec(u):
    if u != -1:
        L.append(u)
        cheminRec(p[u])
cheminRec(u)
print(L)
"""On encapsule dans une fonction chemin(u, p)"""

def chemin(u, p):
    L = []

    def cheminRec(u):
        if u != -1:
            L.append(u)
            cheminRec(p[u])
    cheminRec(u)
    L.reverse()
    return L

print(chemin(7, p))
#p, _ = parcours_en_largeur(G, 0)
#print(chemin(7, p))