换成关注这种单向关系
关注是有向的:一条边只记在关注者那一边。补全 build_follow,然后输出阿泰的粉丝有几个(也就是有几个人关注了他)。 (本题用 g++ -std=c++17 -O0 编译。)
图遍历比树多了什么麻烦
在图上做遍历,比在树上多了一个麻烦:【0】。
怎么解决反复走到的麻烦
第 1 步:从岚出发,先做个记号 第 2 步:第一圈:满、泰 第 3 步:满-泰都已做记号,不再走 第 4 步:第二圈:风 第 5 步:辰始终走不到 岚 满 泰 风 辰 解决办法是【0】。
DFS 和 BFS 各用什么
深度优先和广度优先,分别靠【0】。
从阿岚出发能走到几个人
运行下面这段程序: #include <iostream> #include <string> #include <utility> #include <vector> using names
从北辰出发呢
同一张图,改成从北辰出发。运行下面这段程序: #include <iostream> #include <string> #include <utility> #include <vector>
写一个 BFS
补全 bfs_count:用队列从 start 出发,返回一共能走到几个人(含自己)。⚠️ 这张图里阿岚、小满、阿泰构成一个三角——不记已访问就会一直转圈。 (本题用 g++ -std=c++17 -O0 编译。)
换成 DFS 结果应该一样
补全 dfs_count:把队列换成栈(从末尾取),其余一样。能走到的人数和 BFS 完全相同——走法不同,能到的地方是一样的。 (本题用 g++ -std=c++17 -O0 编译。)
这张图断成了几块
补全 components:数出这张图有几个互相走不通的连通块。做法:对每个还没被走到的人各做一次遍历,做了几次就是几块。 (本题用 g++ -std=c++17 -O0 编译。)
并查集是用来干什么的
第 1 步:p[i]:每人先自己领头 第 2 步:岚-满:根 0 挂到 1 下 第 3 步:岚-泰:根 1 挂到 2 下 第 4 步:满-泰:已是同一块,不动 第 5 步:泰-风:根 2 挂到 3 下 第 6 步:只有 4 号还是自己领头