本文涉及知识点

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]]
解释：
上图为输入所对应的图。

• 节点 0 ，1 和 2 没有任何祖先。
• 节点 3 有 2 个祖先 0 和 1 。
• 节点 4 有 2 个祖先 0 和 2 。
• 节点 5 有 3 个祖先 0 ，1 和 3 。
• 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
• 节点 7 有 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]]
解释：
上图为输入所对应的图。

• 节点 0 没有任何祖先。
• 节点 1 有 1 个祖先 0 。
• 节点 2 有 2 个祖先 0 和 1 。
• 节点 3 有 3 个祖先 0 ，1 和 2 。
• 节点 4 有 4 个祖先 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 Leve(const vector>& neiBo, vector start) { 		vector 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> Two(int n, vector>& edges, bool bDirect, int iBase = 0)  	{ 		vector>  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>> Three(int n, vector>& edges, bool bDirect, int iBase = 0) 	{ 		vector>> 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> Mat(vector>& neiBoMat) 	{ 		vector> 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> getAncestors(int n, vector>& edges) { 				auto neiBo = CNeiBo::Two(n, edges, true); 				vector> 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> edgeList; 		TEST_METHOD(TestMethod1) 		{ 			n = 2, edgeList = { {0,1} }; 			auto res = Solution().getAncestors(n, edgeList); 			AssertV2(vector>{ {}, {0}}, res); 		} 		TEST_METHOD(TestMethod2) 		{ 			n = 2, edgeList = { }; 			auto res = Solution().getAncestors(n, edgeList); 			AssertV2(vector>{ {}, {  }}, 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>{ {}, {}, {}, { 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>{ {}, { 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>{ {}, { 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++**实现。