# Grafo simple: red social
grafo_simple = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice', 'David'],
    'Charlie': ['Alice', 'David', 'Eve'],
    'David': ['Bob', 'Charlie'],
    'Eve': ['Charlie']
}

# Visualización textual

print("Red Social:")
for persona, amigos in grafo_simple.items():
print(f"{persona} es amigo de: {', '.join(amigos)}")

class Grafo:
    def __init__(self, dirigido=False):
        self.dirigido = dirigido
        self.adyacencia = {}

    def agregar_vertice(self, v):
        """Agregar un vértice al grafo"""
        if v not in self.adyacencia:
            self.adyacencia[v] = []

    def agregar_arista(self, v1, v2, peso=None):
        """Agregar una arista entre v1 y v2"""
        self.agregar_vertice(v1)
        self.agregar_vertice(v2)

        # Agregar arista v1 -> v2
        self.adyacencia[v1].append((v2, peso) if peso else v2)

        # Si no es dirigido, agregar v2 -> v1 también
        if not self.dirigido:
            self.adyacencia[v2].append((v1, peso) if peso else v1)

    def __repr__(self):
        lineas = [f"Grafo ({'Dirigido' if self.dirigido else 'No Dirigido'}):"]
        for vertice, vecinos in self.adyacencia.items():
            lineas.append(f"  {vertice} -> {vecinos}")
        return '\n'.join(lineas)

# Ejemplo: Grafo no dirigido (red social)
g_social = Grafo(dirigido=False)
g_social.agregar_arista('Alice', 'Bob')
g_social.agregar_arista('Alice', 'Charlie')
g_social.agregar_arista('Bob', 'David')
print(g_social)

print("\n" + "="*50 + "\n")

# Ejemplo: Grafo dirigido (flujo de programa)
g_flujo = Grafo(dirigido=True)
g_flujo.agregar_arista('inicio', 'proceso1')
g_flujo.agregar_arista('proceso1', 'decision')
g_flujo.agregar_arista('decision', 'proceso2')
g_flujo.agregar_arista('decision', 'fin')
print(g_flujo)

class GrafoMatriz:
    """Grafo usando Matriz de Adyacencia"""
    def __init__(self, n_vertices):
        self.n = n_vertices
        self.matriz = [[0] * n_vertices for _ in range(n_vertices)]

    def agregar_arista(self, u, v):
        self.matriz[u][v] = 1
        self.matriz[v][u] = 1  # No dirigido

    def existe_arista(self, u, v):
        return self.matriz[u][v] == 1

    def vecinos(self, v):
        return [i for i in range(self.n) if self.matriz[v][i] == 1]

    def mostrar(self):
        print("Matriz de Adyacencia:")
        for fila in self.matriz:
            print(fila)

class GrafoLista:
    """Grafo usando Lista de Adyacencia"""
    def __init__(self):
        self.lista = {}

    def agregar_vertice(self, v):
        if v not in self.lista:
            self.lista[v] = []

    def agregar_arista(self, u, v):
        self.agregar_vertice(u)
        self.agregar_vertice(v)
        self.lista[u].append(v)
        self.lista[v].append(u)  # No dirigido

    def existe_arista(self, u, v):
        return v in self.lista.get(u, [])

    def vecinos(self, v):
        return self.lista.get(v, [])

    def mostrar(self):
        print("Lista de Adyacencia:")
        for vertice, vecinos in self.lista.items():
            print(f"{vertice}: {vecinos}")

# Ejemplo comparativo
print("=== Grafo con 4 vértices (0, 1, 2, 3) ===\n")

# Usando Matriz
print("MATRIZ DE ADYACENCIA:")
g_matriz = GrafoMatriz(4)
g_matriz.agregar_arista(0, 1)
g_matriz.agregar_arista(0, 2)
g_matriz.agregar_arista(1, 3)
g_matriz.mostrar()
print(f"Vecinos de 0: {g_matriz.vecinos(0)}")
print(f"¿Existe arista (0,1)? {g_matriz.existe_arista(0, 1)}")

print("\n" + "="*50 + "\n")

# Usando Lista
print("LISTA DE ADYACENCIA:")
g_lista = GrafoLista()
g_lista.agregar_arista(0, 1)
g_lista.agregar_arista(0, 2)
g_lista.agregar_arista(1, 3)
g_lista.mostrar()
print(f"Vecinos de 0: {g_lista.vecinos(0)}")
print(f"¿Existe arista (0,1)? {g_lista.existe_arista(0, 1)}")

# Comparación de espacio
print("\n" + "="*50)
print("COMPARACIÓN DE ESPACIO:")
print(f"Matriz: Siempre 4x4 = 16 posiciones (O(n²))")
print(f"Lista: Solo almacena 4 aristas x 2 = 8 entradas (O(n+m))")
print(f"Ahorro: 50% en este caso (mejor en grafos más esparsos)")

from collections import deque

def bfs(grafo, inicio):
"""
Búsqueda en Amplitud (BFS)

    Retorna:
        visitados: conjunto de vértices visitados
        padres: diccionario de padres (para reconstruir caminos)
        distancias: diccionario de distancias desde inicio
    """
    # Inicializar estructuras
    visitados = set()
    padres = {inicio: None}
    distancias = {inicio: 0}
    cola = deque([inicio])

    print(f"Iniciando BFS desde {inicio}\n")

    while cola:
        # Sacar el primer elemento (FIFO)
        actual = cola.popleft()

        if actual in visitados:
            continue

        # Procesar vértice actual
        visitados.add(actual)
        print(f"Procesando: {actual} (distancia: {distancias[actual]})")

        # Explorar vecinos
        for vecino in grafo.get(actual, []):
            if vecino not in visitados and vecino not in padres:
                padres[vecino] = actual
                distancias[vecino] = distancias[actual] + 1
                cola.append(vecino)
                print(f"  Descubierto: {vecino} (padre: {actual})")

    return visitados, padres, distancias

def reconstruir_camino(padres, inicio, fin):
"""Reconstruir el camino más corto de inicio a fin"""
if fin not in padres:
return None

    camino = []
    actual = fin
    while actual is not None:
        camino.append(actual)
        actual = padres[actual]

    camino.reverse()
    return camino

# Ejemplo: Red de ciudades

ciudades = {
'Madrid': ['Barcelona', 'Valencia', 'Sevilla'],
'Barcelona': ['Madrid', 'Valencia', 'Zaragoza'],
'Valencia': ['Madrid', 'Barcelona', 'Sevilla'],
'Sevilla': ['Madrid', 'Valencia', 'Málaga'],
'Zaragoza': ['Barcelona', 'Bilbao'],
'Málaga': ['Sevilla'],
'Bilbao': ['Zaragoza']
}

print("="*60)
print("BÚSQUEDA EN AMPLITUD (BFS)")
print("="*60 + "\n")

visitados, padres, distancias = bfs(ciudades, 'Madrid')

print("\n" + "="*60)
print("RESULTADOS:")
print("="*60)
print(f"\nVértices visitados: {visitados}")
print(f"\nDistancias desde Madrid:")
for ciudad, dist in sorted(distancias.items(), key=lambda x: x[1]):
print(f" {ciudad}: {dist} pasos")

print(f"\nCamino más corto de Madrid a Bilbao:")
camino = reconstruir_camino(padres, 'Madrid', 'Bilbao')
print(f" {' -> '.join(camino)}")
print(f" Distancia: {len(camino) - 1} pasos")

def dfs_recursivo(grafo, inicio, visitados=None, tiempo=[0],
                  tiempo_entrada=None, tiempo_salida=None, padres=None):
    """
    DFS Recursivo con tiempos de entrada y salida

    Los tiempos son cruciales para:
    - Ordenación topológica
    - Detección de ciclos
    - Clasificación de aristas
    """
    if visitados is None:
        visitados = set()
        tiempo_entrada = {}
        tiempo_salida = {}
        padres = {inicio: None}

    # Marcar como visitado y registrar tiempo de entrada
    visitados.add(inicio)
    tiempo[0] += 1
    tiempo_entrada[inicio] = tiempo[0]
    print(f"Descubriendo {inicio} (tiempo: {tiempo_entrada[inicio]})")

    # Explorar vecinos
    for vecino in grafo.get(inicio, []):
        if vecino not in visitados:
            padres[vecino] = inicio
            dfs_recursivo(grafo, vecino, visitados, tiempo,
                         tiempo_entrada, tiempo_salida, padres)

    # Marcar como procesado y registrar tiempo de salida
    tiempo[0] += 1
    tiempo_salida[inicio] = tiempo[0]
    print(f"Finalizando {inicio} (tiempo: {tiempo_salida[inicio]})")

    return visitados, tiempo_entrada, tiempo_salida, padres

def dfs_iterativo(grafo, inicio):
    """
    DFS Iterativo usando una pila explícita
    """
    visitados = set()
    pila = [inicio]
    padres = {inicio: None}
    orden = []

    print(f"Iniciando DFS desde {inicio}\n")

    while pila:
        # Sacar el último elemento (LIFO)
        actual = pila.pop()

        if actual in visitados:
            continue

        # Procesar vértice
        visitados.add(actual)
        orden.append(actual)
        print(f"Procesando: {actual}")

        # Agregar vecinos a la pila (en orden inverso para mantener orden)
        vecinos = list(grafo.get(actual, []))
        for vecino in reversed(vecinos):
            if vecino not in visitados:
                pila.append(vecino)
                if vecino not in padres:
                    padres[vecino] = actual
                print(f"  Apilando: {vecino}")

    return visitados, orden, padres

# Ejemplo: Sistema de dependencias
dependencias = {
    'main': ['module_a', 'module_b'],
    'module_a': ['utils', 'config'],
    'module_b': ['utils'],
    'utils': ['logger'],
    'config': ['logger'],
    'logger': []
}

print("="*60)
print("BÚSQUEDA EN PROFUNDIDAD (DFS) - VERSIÓN RECURSIVA")
print("="*60 + "\n")

visitados, entrada, salida, padres = dfs_recursivo(dependencias, 'main')

print("\n" + "="*60)
print("Tiempos de entrada y salida:")
print("="*60)
for modulo in sorted(entrada.keys(), key=lambda x: entrada[x]):
    print(f"{modulo}: entrada={entrada[modulo]}, salida={salida[modulo]}")

print("\n" + "="*60)
print("BÚSQUEDA EN PROFUNDIDAD (DFS) - VERSIÓN ITERATIVA")
print("="*60 + "\n")

visitados_iter, orden_iter, padres_iter = dfs_iterativo(dependencias, 'main')

print("\n" + "="*60)
print(f"Orden de visita: {' -> '.join(orden_iter)}")

def ordenacion_topologica(grafo):
    """
    Ordenación Topológica usando DFS
    
    Algoritmo: Etiquetar vértices en orden INVERSO a su tiempo de finalización
    """
    visitados = set()
    pila_ordenada = []
    tiene_ciclo = [False]
    
    def dfs_topologico(v, en_pila):
        """DFS modificado para ordenación topológica y detección de ciclos"""
        if v in en_pila:
            # Back edge encontrada - hay un ciclo
            tiene_ciclo[0] = True
            return
        
        if v in visitados:
            return
        
        visitados.add(v)
        en_pila.add(v)
        
        # Explorar vecinos
        for vecino in grafo.get(v, []):
            dfs_topologico(vecino, en_pila)
        
        en_pila.remove(v)
        # CLAVE: Agregar a la pila cuando se FINALIZA el vértice
        pila_ordenada.append(v)
    
    # Ejecutar DFS desde todos los vértices no visitados
    for vertice in grafo:
        if vertice not in visitados:
            dfs_topologico(vertice, set())
    
    if tiene_ciclo[0]:
        return None  # No hay ordenación topológica (grafo tiene ciclo)
    
    # La pila contiene los vértices en orden inverso al de finalización
    # Invertir para obtener el orden topológico
    return list(reversed(pila_ordenada))

# Ejemplo 1: Cursos con prerrequisitos

cursos = {
'Cálculo 1': [],
'Cálculo 2': ['Cálculo 1'],
'Álgebra Lineal': ['Cálculo 1'],
'Ecuaciones Diferenciales': ['Cálculo 2'],
'Machine Learning': ['Álgebra Lineal', 'Programación'],
'Programación': [],
'Estructuras de Datos': ['Programación'],
'Algoritmos': ['Estructuras de Datos', 'Cálculo 2']
}

print("="*60)
print("ORDENACIÓN TOPOLÓGICA: Cursos con Prerrequisitos")
print("="*60 + "\n")

orden = ordenacion_topologica(cursos)

if orden:
print("Orden válido para tomar los cursos:\n")
for i, curso in enumerate(orden, 1):
prereqs = cursos[curso]
prereq_str = ', '.join(prereqs) if prereqs else 'Ninguno'
print(f"{i}. {curso}")
print(f" Prerrequisitos: {prereq_str}\n")
else:
print("ERROR: El grafo contiene un ciclo (dependencia circular)")

# Ejemplo 2: Sistema con ciclo (inválido)

print("\n" + "="*60)
print("EJEMPLO CON CICLO (No válido para ordenación topológica)")
print("="*60 + "\n")

sistema_ciclico = {
'A': ['B'],
'B': ['C'],
'C': ['A'] # ¡Ciclo!
}

orden_ciclico = ordenacion_topologica(sistema_ciclico)
if orden_ciclico is None:
print("⚠️ ERROR: Dependencia circular detectada")
print("A -> B -> C -> A (ciclo)")
print("\nNo es posible una ordenación topológica válida.")

def encontrar_articulaciones(grafo):
    """
    Encuentra vértices de articulación usando DFS
    
    Usa dos arrays:
    - entry_time: tiempo de descubrimiento
    - low: ancestro más temprano alcanzable
    """
    tiempo = [0]
    visitados = set()
    entry_time = {}
    low = {}
    padres = {}
    articulaciones = set()
    
    def dfs_articulacion(v, padre=None):
        hijos = 0
        visitados.add(v)
        tiempo[0] += 1
        entry_time[v] = low[v] = tiempo[0]
        
        for vecino in grafo.get(v, []):
            if vecino == padre:
                continue
            
            if vecino in visitados:
                # Back edge: actualizar low
                low[v] = min(low[v], entry_time[vecino])
            else:
                # Tree edge
                hijos += 1
                padres[vecino] = v
                dfs_articulacion(vecino, v)
                
                # Actualizar low del padre
                low[v] = min(low[v], low[vecino])
                
                # Verificar si v es articulación
                if padre is None:
                    # Caso raíz: es articulación si tiene más de 1 hijo
                    if hijos > 1:
                        articulaciones.add(v)
                else:
                    # Caso no-raíz: es articulación si algún hijo
                    # no puede alcanzar un ancestro más arriba
                    if low[vecino] >= entry_time[v]:
                        articulaciones.add(v)
    
    # Ejecutar DFS desde todos los componentes
    for vertice in grafo:
        if vertice not in visitados:
            dfs_articulacion(vertice)
    
    return articulaciones, entry_time, low

# Ejemplo: Red de servidores

red_servidores = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B', 'F'],
'E': ['C', 'F'],
'F': ['D', 'E', 'G'],
'G': ['F']
}

print("="*60)
print("VÉRTICES DE ARTICULACIÓN: Red de Servidores")
print("="*60 + "\n")

print("Red de servidores:")
for servidor, conexiones in red_servidores.items():
print(f" {servidor} conectado a: {', '.join(conexiones)}")

articulaciones, entry, low = encontrar_articulaciones(red_servidores)

print("\n" + "="*60)
print("PUNTOS CRÍTICOS DETECTADOS:")
print("="*60 + "\n")

if articulaciones:
print(f"⚠️ Vértices de articulación: {', '.join(sorted(articulaciones))}\n")
print("ADVERTENCIA: La falla de estos servidores causará desconexión de la red.\n")

    for v in sorted(articulaciones):
        print(f"Servidor {v}:")
        print(f"  - Tiempo de entrada: {entry[v]}")
        print(f"  - Ancestro más temprano alcanzable: {low[v]}")
        print()

else:
print("✓ No hay vértices de articulación.")
print(" La red es robusta - ningún servidor único causa desconexión.\n")

# Análisis adicional

print("="*60)
print("ANÁLISIS DE VULNERABILIDAD:")
print("="*60 + "\n")

for v in grafo.keys():
if v in articulaciones:
print(f"❌ {v}: CRÍTICO - Punto único de falla")
else:
print(f"✓ {v}: Seguro - No es punto único de falla")