class Noeud:
    # Variable de classe, pour avoir un affichage plus lisible
    counter = 1
    
    def __init__(self, out):
        assert isinstance(out, list), "Pas une liste"
        assert all(isinstance(n, Noeud) for n in out), "Pas une liste de noeuds"
        self.out = out
        self.cnt = Noeud.counter
        Noeud.counter += 1
        
    def __repr__(self):
        if hasattr(self, 'weight'):
            s = " ".join("→{0}({1})".format(u.cnt,w) for u,w in zip(self.out,self.weight))
        else:
            s = " ".join("→{0}".format(u.cnt) for u in self.out)
        return "Noeud({0}) ".format(self.cnt) + s

class Graphe:
    def __init__(self, noeuds):
        assert isinstance(noeuds, list), "Pas une liste"
        assert all(isinstance(n, Noeud) for n in noeuds), "Pas une liste de noeuds"
        self.noeuds = noeuds
    
    def __repr__(self):
        return "Graphe:\n\t" + "\n\t".join(map(repr, self.noeuds))
    
    def adjacence(self):
        # On remplit la matrice de 0
        mat = [[0 for _ in self.noeuds] for _ in self.noeuds]
        # On met les 1
        for (i,v) in enumerate(self.noeuds):
            if hasattr(v, 'weight'):
                for u,w in zip(v.out,v.weight):
                    mat[i][self.noeuds.index(u)] = w
            else:
                for u in v.out:
                    mat[i][self.noeuds.index(u)] = 1
        return Matrice(mat)

def arbre_couvrant(G):
    for u in G.noeuds:
        u.set = u
    L = []
    for u in G.noeuds:
        for v,w in zip(u.out, u.weight):
            L.append(((u,v),w)) # Arrete (u,v) de poids w
    L.sort(key=(lambda x: x[1]))
    for (u,v),w in L:
        if u.set != v.set:
            Arbre.append((u,v))
            poids += w
            # Fusion des composantes: on remplace u.set par v.set
            for s in G.noeuds:
                if s.set == u.set:
                    s.set = v.set
    return Arbre,poids