图算法

检测从某点出发是否会碰到环

用“颜色法”（递归DFS）

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

检测从某点出发是否会碰到负环

在该点的连通分量上使用(len(reachable)-1)次Bellman-Ford,然后再进行一次Bellman-Ford,如果还能松弛，则说明有负环存在 连通分量可用BFS/DFS求。 这里展现的是DFS求解：

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就是可达的连通分量
	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

检测整张图上是否有环

对每个未处理(color=0)的节点调用一遍dfs（颜色法）

检测整张图上是否有负环

在图上使用(len(graph)-1)次Bellman Ford，然后再进行一次Bellman-Ford，如果还能松弛，说明有负环存在。