Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def make_set (lista):
- return {vertice:comp for comp,vertice in enumerate(lista[0])}
- def find (elem, disjoint):
- for vertice, comp in disjoint.items():
- if vertice == elem:
- return comp
- def union (id_1, id_2, disjoint):
- for vertice, comp in disjoint.items():
- if comp == id_2:
- disjoint[vertice] = id_1
- return disjoint
- def componentes_conexas (lista):
- disjoint = make_set(lista)
- for arista in lista[1]:
- vert1, vert2 = arista[0], arista[1]
- comp1 = find (vert1, disjoint)
- comp2 = find (vert2, disjoint)
- if comp1 != comp2:
- disjoint = union(comp1, comp2, disjoint)
- #Crea una lista de las etiquetas de las componentes sin repeticiones.
- lista_etiquetas = []
- for etiqueta in disjoint.values():
- if etiqueta not in lista_etiquetas:
- lista_etiquetas.append(etiqueta)
- #Para cada vértice, busca el valor de su componente conexa y lo agrega a la lista correspondiente.
- lista_componentes = [[] for x in range(len(lista_etiquetas))]
- for vertice,comp in disjoint.items():
- for indice,etiqueta in enumerate(lista_etiquetas):
- if etiqueta == comp:
- (lista_componentes[indice]).append(vertice)
- break
- return lista_componentes
- def main():
- lista = [['A', 'B', 'C', 'D', 'E', 'F'] , [['A','B'], ['A','C'], ['C','B'], ['D','E'], ['D','D']]]
- print(componentes_conexas(lista))
- if __name__ == '__main__':
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement