从北辰出发呢
同一张图,改成从北辰出发。运行下面这段程序: NAMES = ["阿岚", "小满", "阿泰", "南风", "北辰"] EDGES =
写一个 BFS
补全 bfs_count:用队列从 start 出发,返回一共能走到几个人(含自己)。 ⚠️ 这张图里阿岚、小满、阿泰构成一个三角——不记已访问就会一直转圈。
换成 DFS,结果应该一样
补全 dfs_count:把队列换成栈(取末尾而不是队头),其余一样。 能走到的人数和 BFS 完全相同——走法不同,能到的地方是一样的。
这张图断成了几块
补全 components:数出这张图有几个互相走不通的连通块。 做法:对每个还没被走到的人各做一次遍历,做了几次就是几块。
并查集是用来干什么的
并查集解决的问题是【0】。
路径压缩是什么意思
并查集里的"路径压缩"指的是【0】。
合并之后这两个人连通了吗
一开始每个人自己一块。运行下面这段程序: NAMES = ["阿岚", "小满", "阿泰", "南风", "北辰"] EDGES = [(
一共有几块
同样合并完之后。运行下面这段程序: NAMES = ["阿岚", "小满", "阿泰", "南风", "北辰"] EDGES = [(&qu
写一个 find(带路径压缩)
补全 find:一路往上找到根,顺手把沿途的点往上挂一层。 这次查的是一条手工搭出来的链,输出根是谁。
写一个 union
补全 union:把两个点所在的两块合成一块。 四条关系全合并完之后,输出阿岚和南风是不是同一块。