Advertisement
tomasfdel

Complementos I Práctica Lab 2

Sep 6th, 2017
406
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.58 KB | None | 0 0
  1. def make_set (lista):
  2.     return {vertice:comp for comp,vertice in enumerate(lista[0])}
  3.    
  4. def find (elem, disjoint):
  5.     for vertice, comp in disjoint.items():
  6.         if vertice == elem:
  7.             return comp
  8.            
  9. def union (id_1, id_2, disjoint):
  10.     for vertice, comp in disjoint.items():
  11.         if comp == id_2:
  12.             disjoint[vertice] = id_1
  13.     return disjoint
  14.    
  15. def componentes_conexas (lista):
  16.     disjoint = make_set(lista)
  17.     for arista in lista[1]:
  18.         vert1, vert2 = arista[0], arista[1]
  19.         comp1 = find (vert1, disjoint)
  20.         comp2 = find (vert2, disjoint)
  21.         if comp1 != comp2:
  22.             disjoint = union(comp1, comp2, disjoint)
  23.  
  24.     #Crea una lista de las etiquetas de las componentes sin repeticiones.
  25.     lista_etiquetas = []
  26.     for etiqueta in disjoint.values():
  27.         if etiqueta not in lista_etiquetas:
  28.             lista_etiquetas.append(etiqueta)
  29.    
  30.     #Para cada vértice, busca el valor de su componente conexa y lo agrega a la lista correspondiente.
  31.     lista_componentes = [[] for x in range(len(lista_etiquetas))]
  32.     for vertice,comp in disjoint.items():
  33.         for indice,etiqueta in enumerate(lista_etiquetas):
  34.             if etiqueta == comp:
  35.                 (lista_componentes[indice]).append(vertice)
  36.                 break
  37.            
  38.     return lista_componentes
  39.            
  40.            
  41. def main():
  42.     lista = [['A', 'B', 'C', 'D', 'E', 'F'] , [['A','B'], ['A','C'], ['C','B'], ['D','E'], ['D','D']]]
  43.     print(componentes_conexas(lista))    
  44.    
  45. if __name__ == '__main__':
  46.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement