本文涉及知识点

C++图论

LeetCode1042. 不邻接植花

有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。
另外，所有花园 最多 有 3 条路径可以进入或离开.
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
示例 1：
输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]
示例 2：
输入：n = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：
输入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
提示：
1 <= n <= 10⁴
0 <= paths.length <= 2 * 10⁴
paths[i].length == 2
1 <= xi, yi <= n
xi != yi
每个花园 最多 有 3 条路径可以进入或离开

图论

以任意顺序处理节点都可以，因为最多三个临接点，所有1到4中最多3个数使用，使用未使用的那个数就可以了。
建立临接表的时候，将1到n，改成0到n-1。

代码

核心代码

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<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
				auto neiBo = CNeiBo::Two(n, paths, false, 1);
				vector<int> ans(n);
				for (int i = 0; i < n; i++) {
					bool use[5] = { false };
					for (const auto& next : neiBo[i]) {		
						use[ans[next]] = true;
					}
					for (int j = 1; j <= 4; j++) {
						if (!use[j]) { ans[i] = j; break; }
					}
				}
				return ans;
			}
		};

单元测试

int n;
		vector<vector<int>> paths;
		void Check(int n, vector<vector<int>>& paths,vector<int> ans) {
			auto neiBo = CNeiBo::Two(n, paths, false, 1);
			for (int i = 0; i < n; i++) {	
				for (const auto& next : neiBo[i]) {
					Assert::IsTrue(ans[i] != ans[next]);
				}			
			}
		}
		TEST_METHOD(TestMethod11)
		{
			n = 3, paths = { {1,2},{2,3},{3,1} };
			auto res = Solution().gardenNoAdj(n, paths);
			Check(n, paths, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, paths = { {1,2},{3,4} };
			auto res = Solution().gardenNoAdj(n, paths);
			Check(n, paths, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 4, paths = { {1,2},{2,3},{3,4},{4,1},{1,3},{2,4} };
			auto res = Solution().gardenNoAdj(n, paths);
			Check(n, paths, res);
		}