import numpy as np

## Exercice 1 — représentations

L = [[1], [0, 1, 3, 4], [1, 3], [2], [0, 3]]

Mat_adj = [
    [0, 1, 0, 1, 1, 0, 0, 0, 0, 0],  # 0 : 1, 3, 4
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 0],  # 1 : 0, 2, 4
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],  # 2 : 1, 8
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 0],  # 3 : 0, 8
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],  # 4 : 0, 1
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # 5 isolé
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],  # 6 : 7, 8
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],  # 7 : 6
    [0, 0, 1, 1, 0, 0, 1, 0, 0, 1],  # 8 : 2, 3, 6, 9
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],  # 9 : 8
]
# Nombre de sommets = len(Mat_adj) (matrice carrée).

M = [
    [0, 1, 0, 0, 1],
    [0, 0, 1, 1, 1],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0],
]

Dict_adj = {
    "A": ["B"],
    "B": ["B", "E", "D"],
    "C": ["B", "D"],
    "D": ["C"],
    "E": ["A", "D"],
}
# Voisins de B : Dict_adj["B"]
# Sommets : list(Dict_adj.keys())
Dict_adj["D"].append("E")


## Exercice 2 — Nombre d'arcs : somme des coefficients de la matrice.

def nombre_d_arcs(M):
    n = len(M)
    cpt = 0
    for i in range(n):
        for j in range(n):
            cpt = cpt + M[i][j]
    return cpt


## Exercice 3 — Modes de représentation

def liste_vers_matrice(L):
    n = len(L)
    M = []
    for i in range(n):
        ligne = n * [0]
        for j in L[i]:
            ligne[j] = 1
        M.append(ligne)
    return M

def matrice_vers_liste(M):
    n = len(M)
    L = []
    for i in range(n):
        voisins = []
        for j in range(n):
            if M[i][j] == 1:
                voisins.append(j)
        L.append(voisins)
    return L


## Exercice 4 — Degré, successeurs, prédécesseurs

def degre_sortant_liste(L, s):
    return len(L[s])

def degre_sortant_matrice(M, s):
    cpt = 0
    for j in range(len(M)):
        cpt = cpt + M[s][j]
    return cpt

def successeurs(M, s):
    voisins = []
    for v in range(len(M)):
        if M[s][v] == 1:
            voisins.append(v)
    return voisins

def degre_entrant(M, s):
    cpt = 0
    for i in range(len(M)):
        cpt = cpt + M[i][s]
    return cpt

def predecesseurs(M, s):
    voisins = []
    for v in range(len(M)):
        if M[v][s] == 1:
            voisins.append(v)
    return voisins


## Exercice 5 — Parcours en largeur

def parcours_en_largeur(M, s):
    a_visiter = [s]
    distances = len(M) * [np.inf]
    distances[s] = 0
    while a_visiter != []:
        sommet = a_visiter.pop(0)
        for v in successeurs(M, sommet):
            if v not in a_visiter and distances[v] == np.inf:
                a_visiter.append(v)
                distances[v] = distances[sommet] + 1
    return distances

def accessibles(M, s):
    distances = parcours_en_largeur(M, s)
    sommets = []
    for v in range(len(M)):
        if distances[v] != np.inf:
            sommets.append(v)
    return sommets

def existe_chemin(M, s, t):
    return t in accessibles(M, s)

def est_connexe(M):
    # Graphe non orienté : on part d'un sommet et on vérifie qu'on atteint tous.
    return len(accessibles(M, 0)) == len(M)