【C++BFS算法】2192. 有向无环图中一个节点的所有祖先_业界新闻

发布时间:2024-08-08 02:31

阅读量:0

本文涉及知识点

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<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); 		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功