【C++图论拓扑排序】2392. 给定条件下构造矩阵|1960

本文涉及知识点

C++图论拓扑排序

LeetCode2392. 给定条件下构造矩阵

给你一个正整数 k ，同时给你：
一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。
两个数组里的整数都是 1 到 k 之间的数字。
你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要恰好出现一次。剩余的数字都是 0 。
矩阵还需要满足以下条件：
对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的行必须在数字 belowi 所在行的上面。
对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的列必须在数字 righti 所在列的左边。
返回满足上述要求的任意矩阵。如果不存在答案，返回一个空的矩阵。
示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：

数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。
示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：
2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 10⁴
rowConditions[i].length == colConditions[i].length == 2
1 <= abovei, belowi, lefti, righti <= k
abovei != belowi
lefti != righti

通过排序

行调整完毕后，任意调整各数所在列，并不影响各数所在行。
先处理行： i1在i2上面，则i1指向i2，求 0到10的拓扑序，拓扑序小的行号大。
在处理列：i1在i2左边，则i1指向i2，求 0到10的拓扑序，拓扑序小的列号大。
如果有环，则拓扑序不完整，返回空矩阵。

代码

核心代码

class CTopSort
{
public:	template <class T = vector<int> >void Init(const vector<T>& vNeiBo,bool bDirect  ){const int iDelOutDeg = bDirect ? 0 : 1;m_c = vNeiBo.size();m_vBackNeiBo.resize(m_c);vector<int> vOutDeg(m_c);for (int cur = 0; cur < m_c; cur++){vOutDeg[cur] = vNeiBo[cur].size();	for (const auto& next : vNeiBo[cur]){m_vBackNeiBo[next].emplace_back(cur);}}vector<bool> m_vHasDo(m_c);queue<int> que;for (int i = 0; i < m_c; i++){if ( vOutDeg[i] <= iDelOutDeg){m_vHasDo[i] = true;if (OnDo(i)) {que.emplace(i);}}}while (que.size()){const int cur = que.front();que.pop();for (const auto& next : m_vBackNeiBo[cur]){if (m_vHasDo[next] ){continue;}				vOutDeg[next]--;if (vOutDeg[next] <= iDelOutDeg ){m_vHasDo[next] = true;if (OnDo(next)) {que.emplace(next);}}}};}int m_c;
protected:virtual bool OnDo( int cur) = 0;vector<vector<int>> m_vBackNeiBo;	};class CMyTopSort :public CTopSort{public:		virtual bool OnDo(int cur) override{if( 0 != cur )m_ans.emplace_back(cur);return true;}			vector<int> m_ans;};class Solution {public:vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {vector<vector<int>> neiBo1(k + 1), neiBo2(k + 1);for (const auto& v : rowConditions) {neiBo1[v[0]].emplace_back(v[1]);}for (const auto& v : colConditions) {neiBo2[v[0]].emplace_back(v[1]);}CMyTopSort topSort1;topSort1.Init(neiBo1, true);CMyTopSort topSort2;topSort2.Init(neiBo2, true);if (topSort1.m_ans.size() < k ) { return {}; }if (topSort2.m_ans.size() < k ) { return {}; }vector<int> rows(k+1), cols(k+1);for (int i = 0; i < topSort1.m_ans.size(); i++) {rows[topSort1.m_ans[i]] =  k - 1 - i;}for (int i = 0; i < topSort2.m_ans.size(); i++) {cols[topSort2.m_ans[i]] = k-1-i;}vector<vector<int>> ans(k, vector<int>(k));for (int i = 1; i <= k; i++) {ans[rows[i]][cols[i]] = i ;}return ans;}};

单元测试

	void Check(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions,const vector<vector<int>>& mat) {vector<int> rows(k+1, -1), cols(k+1, -1);for (int r = 0; r < k; r++) {for (int c = 0; c < k; c++) {const int i = mat[r][c];if (0 == i)continue;if ((-1 != rows[i] || (-1 != cols[i]))) { Assert::IsTrue(false); return; }rows[i] = r;cols[i] = c;}}for (int i = 1; i <= k; i++) {if ((-1 == rows[i] || (-1 == cols[i]))) { Assert::IsTrue(false); return; }}for (const auto& v : rowConditions) {Assert::IsTrue(rows[v[0]] < rows[v[1]]);}for (const auto& v : colConditions) {Assert::IsTrue(cols[v[0]] < cols[v[1]]);}}int k;vector<vector<int>> rowConditions,  colConditions;TEST_METHOD(TestMethod11){k = 3, rowConditions = { {1,2},{3,2} }, colConditions = { {2,1},{3,2} };auto res = Solution().buildMatrix(k, rowConditions, colConditions);Check(k, rowConditions, colConditions,res);}TEST_METHOD(TestMethod12){k = 3, rowConditions = { {1,2},{2,3},{3,1},{2,3} }, colConditions = { {2,1} };auto res = Solution().buildMatrix(k, rowConditions, colConditions);AssertV2(vector<vector<int>>{}, res);}

扩展阅读

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