Negative Cycles (Advanced)

def detect_negative_cycle(graph, start):
    """Detect negative cycle using Bellman-Ford"""
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    
    # Relax V-1 times
    for _ in range(n - 1):
        for u, v, weight in graph:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # Check for negative cycle
    for u, v, weight in graph:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return True  # Negative cycle detected
    
    return False

def find_negative_cycle(graph, start):
    """Find vertices in negative cycle"""
    n = len(graph)
    dist = [float('inf')] * n
    parent = [-1] * n
    dist[start] = 0
    
    # Relax V times
    for _ in range(n):
        for u, v, weight in graph:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                parent[v] = u
    
    # Find vertex in negative cycle
    for u, v, weight in graph:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            # Trace back to find cycle
            cycle = []
            visited = set()
            current = v
            while current not in visited:
                visited.add(current)
                cycle.append(current)
                current = parent[current]
            cycle.append(current)
            return cycle[cycle.index(current):]
    
    return None