问题来源于做题 力扣-顺丰科技智慧物流校园技术挑战赛 中的第一题。
没阅读《剑指Offer》之前看到题时不会做，在阅读过程中有自己的解题想法，也看到《剑指Offer》中提到的解法。先按自己的想法实现，结果发现了自己想法的误区，所以在这里记录一下误区及原因，以及正确的解法。
如下图，红线为故意加入的一个导致有向图中形成环。
入度和出度
- 入度统计的是有多少箭头指向自己。
- 出度统计的是自己有多少箭头指向别人。
如上图中节点 8 被两个箭头指向，所以它的入度为 2；有一个指向 12 的箭头，所以出度为 1。同理，上图节点 5入度为 1，出度为 2。
错误的想法
考虑到有环，所以直观的想法是：沿着路走，如果某条路一直导致重复走某些节点，那么就证明存在环。
细节：
- 怎么沿着路走：用广度优先算法（队列）。可以。
- 怎么确定有环的具体条件：Em...（支支吾吾）根据...入度次数？
问题就出在判断有环的条件上，你不好判断某几个点是一直在循环。考虑如下几点：
- 如果 A 点到 B 点的路径有 3 中，B 到 C 的路径有 5 种，那么 A 到 C 一共有 15 种路径。如果广度优先算法中不限制访问过的点再次访问，那么从到 C 点就至少有 15 种走法。如何定上限就是个问题。
- 上步中，如果要限制每个点都被走一次也不能判断有环。极端地例子如 A 能走向 B 和 C，B 能走向 C，C 也能走向 B，怎么判断这种环？
- 那统计边的次数呢？……
考虑边是正确的想法。但如何判断有环条件还需要进一步考虑细节：
- 规定每个边只走一次？每个边都会走到。单纯这个条件没法判断
- 规定每个边只走一次，再加上每个点只走一次呢？也不行，思考一下可以知道点上不能限制只走一次。
- 规定每个边只走一次，每个点上只走它的入度次？这个好像可以。验证一下好像还少个 “没有路时是否为终点” 的条件。
- 规定每个边只走一次，每个点上只走它的入度次，且最后无路时总是走向终点。若不是终点，则证明有环。哎，这个好像可以。
但上方最后一个方案还是有问题的：没有考虑 “孤岛” 的存在，如只有一个 A 节点没有入度也没有出度，或 A、B 节点相互有向连接。如果加逻辑判断又该怎么加呢？
此时已经差不多很接近正确的解法了，具体参考下节吧。
正确的解法
《剑指Offer-专项突击版》在图-拓扑排序 一节中有提到解法。文中主要讲的是拓扑排序，我这里转化一下针对于查环描述：
每次从有向图中取出一个入度为 0 的节点删除，同时删除该节点及所有以他为起点的边，若最终图为空则证明无环，最终非空则证明有环。
原文：“一种常用的拓扑排序算法是每次从有向无环图中取出一个入度为 0 的节点添加到拓扑排序序列之中，然后删除该节点及所有以它为起点的边。重复这个步骤，直到图为空或图中不存在入度为 0 的节点。如果最终图为空，那么图是有向无环图，此时就找到了该图的一个拓扑排序序列。如果最终图不为空并且已经不存在入度为 0 的节点，那么图中一定有环。”
为什么呢？：我们来单独考虑一个单环，那么环中每一个点都是入度为 1，出度也为 1，即不可能入度为 0。按上面删环的描述过程，如果环存在，这个环中的的每个点都无法有机会变成入度为 0 的点，因此就证明了环的存在。
哈，类似于环中象棋中的“连环马”战术了：每个节点相互看守。“入度为 0”这只矛根本无从下手（无法入环）。
解题思路及代码
解题思路
整体思路：通过每次删除入度为 0 的边，最后判断是否还有删除不到的边存在。删除不到就是因为不存在入度 0 的边了。若存在就是有环，否则无环。
细节：
- 用 边的集合 来表示此图，因为要有删除边的操作。
- 要记录所有点的入度，所以用个 map 记录入度（inCounts）
- 要查找下一个节点，所以要用个 map 记录路径的两点
- 入度为 0 的点是要分析的点，所以用个队列记录所有入度为 0 的点（heads）
综上：每次通过入度为 0 的 heads 数组中取一个，遍历它的下一个节点 target，删除此路 edge，并更新 target 的入度（减一），若 target 入度为 0，加入到 heads 中，以备下次分析到。
解题代码
目前只记录了个人从书上获得的解法及自己写的思路。还需要看看书中是不是有其他细节的有环，或其他人的代码的方法。（力扣上用 dfs 遍历看一下）
// parseToMap parse edges to map[[2]int]struct{}
func parseToMap(graph string) map[[2]int]struct{} {
paths := strings.Split(graph, ",")
arr := make(map[[2]int]struct{}, len(paths))
for _, path := range paths {
temp := strings.Split(path, "->")
a, _ := strconv.Atoi(temp[0])
b, _ := strconv.Atoi(temp[1])
arr[[2]int{a, b}] = struct{}{}
}
return arr
}
func hasCycle(graph string) bool {
// parseToMap parse edges to map[[2]int]struct{}
// 因为要有线的删除，所以用 map 存储边集
edges := parseToMap(graph) // 边集
// 记录点的指向
paths := make(map[int][]int, 100)
for edge := range edges {
paths[edge[0]] = append(paths[edge[0]], edge[1])
}
// 计算入度
inCounts := make(map[int]int, 100) // 入度：起始点=>入度
for edge, _ := range edges {
inCounts[edge[1]]++ // 入度为箭头的箭头（头部），只能统计到非零入度的点
inCounts[edge[0]] = inCounts[edge[0]] + 0 // 因为上步中统计不到入度为 0 的点（注意点）
}
// 入度为 0 的点就是 heads
heads := make([]int, 0)
for node, count := range inCounts {
if count == 0 {
heads = append(heads, node)
}
}
// 按 heads 遍历（把 heads 当队列用，动态变化）
for len(heads) > 0 {
var head int
head, heads = heads[0], heads[1:]
for _, target := range paths[head] {
inCounts[target]-- // 入度 - 1
delete(edges, [2]int{head, target}) // 删除图中的边
if inCounts[target] == 0 { // 入度减为 0，成为新的 head
heads = append(heads, target)
}
}
}
// fmt.Println(inCounts)
// fmt.Println(edges)
return len(edges) > 0
}
