本文涉及知识点
C++BFS算法
LeetCode2192. 有向无环图中一个节点的所有祖先
给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。
示例 1：
输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释：
上图为输入所对应的图。
示例 2：
输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入所对应的图。
提示：
1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。
C++BFS
本问题 ⟺ \iff ⟺ 求各节点的后代，BFS各节点的层次，层次不是-1，就是后代。求一个节点后代的时间复杂度：O(m) ,m = edges.length，总时间复杂度为：O(nm)。 空间复杂度：O(m)，每次求节点后代，都重新分配内存。
代码
核心代码
class CBFSLeve {public :static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {vector<int> leves(neiBo.size(), -1);for (const auto& s : start) {leves[s] = 0;}for (int i = 0; i < start.size(); i++) {for (const auto& next : neiBo[start[i]]) {if (-1 != leves[next]) { continue; }leves[next] = leves[start[i]]+1;start.emplace_back(next);}}return leves;}};class CNeiBo{public:static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) {vector<vector<int>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}};class Solution {public:vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {auto neiBo = CNeiBo::Two(n, edges, true);vector<vector<int>> ret(n);for (int i = 0; i < n; i++) {auto leve = CBFSLeve::Leve(neiBo, { i });for (int j = 0; j < leve.size(); j++) {if (leve[j]<=0) { continue; }ret[j].emplace_back(i);}}return ret;}};单元测试
int n;vector<vector<int>> edgeList;TEST_METHOD(TestMethod1){n = 2, edgeList = { {0,1} };auto res = Solution().getAncestors(n, edgeList);AssertV2(vector<vector<int>>{ {}, {0}}, res);}TEST_METHOD(TestMethod2){n = 2, edgeList = { };auto res = Solution().getAncestors(n, edgeList);AssertV2(vector<vector<int>>{ {}, { }}, res);}TEST_METHOD(TestMethod15){n = 8, edgeList = { {0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6} };auto res = Solution().getAncestors(n, edgeList);AssertV2(vector<vector<int>>{ {}, {}, {}, { 0,1 }, { 0,2 }, { 0,1,3 }, { 0,1,2,3,4 }, { 0,1,2,3 }}, res);}TEST_METHOD(TestMethod16){n = 5, edgeList = { {0,1},{0,2},{0,3},{0,4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4} };auto res = Solution().getAncestors(n, edgeList);AssertV2(vector<vector<int>>{ {}, { 0 }, { 0,1 }, { 0,1,2 }, { 0,1,2,3 }}, res);}TEST_METHOD(TestMethod17){n = 8, edgeList ={ {0,7},{7,6},{0,3},{6,3},{5,4},{1,5},{2,7},{3,5},{3,1},{0,5},{7,5},{2,1},{1,4},{6,1} };auto res = Solution().getAncestors(n, edgeList);AssertV2(vector<vector<int>>{ {}, { 0,2,3,6,7 }, {}, { 0,2,6,7 }, { 0,1,2,3,5,6,7 }, { 0,1,2,3,6,7 }, { 0,2,7 }, { 0,2 }}, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
