# Question 1 :

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

# Question 2 :
# On a besoin de faire un test d'appartenance à une liste.

def appartient(x,L):
    for elem in L :
        if x == elem :
            return True
    return False

def sansBoucleLA(graphe):
    for s in range(len(graphe)) :
        if appartient(s,graphe[s]) :
            return False
    return True

# Complexité en O(|S|+|A|) bien entendu ^_^

# Question 3 :

def degreSortantLA(graphe):
    out = []
    for sommet in graphe :
        out.append(len(sommet))
    return out

def degreSortantLAcondense(graphe):
    return [len(s) for s in graphe]

# Complexité en O(|S|) bien entendu ^_^

# Question 4 :

def degreEntrantLA(graphe):
    n = len(graphe)
    out = [0 for i in range(n)]
    for sommet in graphe :
        for voisin in sommet :
            out[voisin] += 1
    return out

# Même complexité qu'à la question 2.

# Question 5 :

def VersOrienteLA(graphe):
    n = len(graphe)
    out = [[] for s in range(n)]
    for i in range(n):
        for voisin in graphe[i]:
            if i<voisin :
                out[i].append(voisin)
    return out

# Question 6 :

def VersNonOrienteLA(graphe):
    n = len(graphe)
    out = [[] for sommet in graphe]
    for i in range(n) :
        for voisin in graphe[i]:
            if not appartient(voisin,out[i]):
                out[i].append(voisin)
            if not appartient(i,out[voisin]):
                out[voisin].append(i)
    return out

# Question 7 :

def estCliqueLA(graphe,liste_sommets_X):
    out = True
    n = len(liste_sommets_X)
    for i in range(n) :
        for j in range(i+1,n) :
            if not appartient(j,graphe[i]):
                out = False
    return out

# Question 8 :

def bienColorierLA(graphe,couleur) :
    out = True
    for sommet in range(len(graphe)) :
        for voisin in graphe[sommet] :
            if couleur[voisin] == couleur[sommet] :
                out = False
    return out

# Question 9 :
M1 = [[0,0,0,1,0,0,0],
      [0,0,0,0,0,0,0],
      [1,1,0,0,0,1,0],
      [0,0,0,0,1,0,0],
      [0,0,0,0,0,0,0],
      [0,0,0,1,0,0,0],
      [0,0,0,1,0,0,0]
     ]

M1 = [[0,1,0,1,0,0,0,0],
      [1,0,0,0,0,1,1,1],
      [0,0,0,0,1,1,0,0],
      [1,0,0,0,1,0,0,0],
      [0,0,1,1,0,1,0,1],
      [0,1,1,0,1,0,0,1],
      [0,1,0,0,0,0,0,1],
      [0,1,0,0,1,1,1,0]
     ]

# Question 10 :

def sansBoucleMA(graphe):
    for i in range(len(graphe)) :
        if graphe[i][i] == 1 :
            return False
    return True

# Complexité en O(|S|) bien entendu ^_^

# Question 11 :

def degreSortantMA(graphe):
    n = len(graphe)
    out = [0 for i in range(n)]
    for i in range(n):
        for j in range(n):
            if graphe[i][j] == 1 :
                out[i] += 1
    return out

# Complexité en O(|S|²)

# Question 12 :

def degreEntrantMA(graphe):
    n = len(graphe)
    out = [0 for i in range(n)]
    for j in range(n):
        for i in range(n):
            if graphe[i][j] == 1 :
                out[j] += 1
    return out

# Complexité en O(|S|²)

# Question 13 :

def VersOrienteMA(graphe):
    out = []
    for i in range(len(graphe)) :
        temp = []
        for j in range(len(graphe[i])) :
            if j<i :
                temp.append(graphe[i][j])
            else :
                temp.append(0)
        out.append(temp)
    return out

# Question 14 :

def VersNonOrienteMA(graphe):
    out = []
    for i in range(len(graphe)) :
        temp = []
        for j in range(len(graphe[i])) :
            if graphe[i][j] == 1 or graphe[j][i] == 1 :
                temp.append(1)
            else :
                temp.append(0)
        out.append(temp)
    return out

# Question 15 :

def estCliqueMA(graphe,liste_sommets_X) :
    out = True
    n = len(liste_sommets_X)
    for i in range(n) :
        for j in range(i+1,n) :
            if not graphe[liste_sommets_X[i]][liste_sommets_X[j]]==1:
                out = False
    return out

# Question 16 :

def bienColorierMA(graphe,couleur) :
    out = True
    n = len(graphe)
    for i in range(n) :
        for j in range(n) :
            if graphe[i][j] == 1 and couleur[i] == couleur[j] :
                out = False
    return out

# Question 17 :

def creuseVersDense(graphe):
    n = len(graphe)
    out = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for voisin in graphe[i]:
            out[i][voisin] = 1
    return out

# Question 18 :

def DenseVersCreuse(graphe):
    n = len(graphe)
    out = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if graphe[i][j] == 1 :
                out[i].append(j)
    return out