本文涉及知识点

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