# -*- coding: utf-8 -*-
"""
Created on Tue Jan 24 23:35:49 2023

@author: dconduche
"""

import collections as co



## Q1
print("QUESTION 1")
#import collections as co

f = co.deque()
f.append(0)
f.append(3)
f.append(1)
print(f)
f.pop()
print(f)
f.popleft()
print(f)

## Q2
print("QUESTION 2")
#G = [[]] * 8
#G[0] = [1, 3, 7]
#G[1] = [2, 5]
#G[2] = [3]
#G[3] = [1]
#G[4] = [0]
#G[5] = [6, 7]
#G[6] = [5, 1]
#G[7] = [4]
#print(G)
G = [[1, 3, 7], [2, 5], [3], [1], [0], [6, 7], [5, 1], [4]]


## Q3
print("QUESTION 3")
n = len(G)
s = 0        # Toujours des variables, partout des variables

c = ['b'] * n
f = co.deque()
p = [-1] * n
d = [-1] * n

# Le sommet de départ :
f.append(s)
c[s] = 'g'
d[s] = 0

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

## Q4
print("QUESTION 4")
u = 0
print('G[u] =', G[u])


## Q5
print("QUESTION 5")

#u = 0
u = f.popleft()
for a in G[u]:
    if c[a] == 'b':
        c[a] = 'g'
        f.append(a)
        p[a] = u
        d[a] = d[u] + 1
c[u] = 'n'

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

## Q6
print("QUESTION 6")

def affiche(c, f, p, d):
    print('c =', c)
    print('f =', f)
    print('p =', p)
    print('d =', d)

# On réinitialise :
n = len(G)
s = 0        # Toujours des variables, partout des variables

c = ['b'] * n
f = co.deque()
p = [-1] * n
d = [-1] * n
# Le sommet de départ :
f.append(s)
c[s] = 'g'
d[s] = 0

while len(f) > 0:
    u = f.popleft()
    for a in G[u]:
        if c[a] == 'b':
            c[a] = 'g'
            f.append(a)
            p[a] = u
            d[a] = d[u] + 1
    c[u] = 'n'
    print(u)
    affiche(c, f, p, d)

## Q7
print("QUESTION 7")


def parcours_en_largeur(G, s):
    n = len(G)
    # initialisation
    c = ['b'] * n
    f = co.deque()
    p = [-1] * n
    d = [-1] * n
    # Le sommet de départ :
    f.append(s)
    c[s] = 'g'
    d[s] = 0    
    while len(f) > 0:
        u = f.popleft()
        for a in G[u]:
            if c[a] == 'b':
                c[a] = 'g'
                f.append(a)
                p[a] = u
                d[a] = d[u] + 1
        c[u] = 'n'
    return (p, d)

print(parcours_en_largeur(G, 0))

## Q8
print("QUESTION 8")

""" n = |S|
Il y 3n (+2) affectations lors de l'initialisation. 
 la boucle while dure autant qu'il y a d'éléments qui passent dans f
 Or chaque sommet passe dans f une fois et une seule (passage de blanc à gris)
 Donc il y a exactement n passages dans la boucle while
Plus généralement (boucles while et for), il y a autant d'affectations que
de passage de blanc à gris (c[a], p[a], d[a]), donc n
de passage de gris à noir (c[u]='n') donc n
Ainsi le nombre d'affectation est en O(|S|)

Pour la taille des boucles, les boucles for parcourent les arêtes partant de u,
et u parcourt l'ensemble des sommets. On parcourt donc l'ensemble des arêtes.

La complexité est donc en O(|S|+|A|)"""