图算法

def has_cycle(n,start,graph):
    color = [0] * n
    def dfs(i):
        color[i] = 1
        for v in graph[i]:
            if color[v] == 1:
                return True
            if color[v] = 0:
                if dfs(v):
                    return True
        color[i] = 2
        return False

def detect_neg(n,start,graph):
    reachable = set([start])
    deque_bfs = deque([start])
    while deque_bfs:
        u = deque_bfs.popleft()
        for v in graph[u]:
            if v not in reachable:
                reachable.add(v)
                deque_bfs.append(v)
    # 这样得到的reachable就是可达的连通分量
<div markdown="1" style="margin-top: -30px; font-size: 0.75em; opacity: 0.7;">
:material-circle-edit-outline: 约 160 个字 :fontawesome-solid-code: 42 行代码 :material-clock-time-two-outline: 预计阅读时间 1 分钟
</div>
    dist = {u:float('inf') for u in reachable}
    dist[start] = 0
    for _ in range(len(reachable) - 1):
        updated = False
        for u in reachable:
            if dist[u] == float('inf'):
                continue
            for v,w in graph[u]
                if v in reachable and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    updated = True
        if !updated:
            break
    for u in reachable:
            if dist[u] == float('inf'):
                continue
            for v,w in graph[u]
                if v in reachable and dist[u] + w < dist[v]:
                    return True
    return False