1. 題目

有 N 個花園，按從 1 到 N 標記。在每個花園中，你打算種下四種花之一。

paths[i] = [x, y] 描述了花園 x 到花園 y 的雙向路徑。

另外，沒有花園有 3 條以上的路徑可以進入或者離開。

你需要為每個花園選擇一種花，使得通過路徑相連的任何兩個花園中的花的種類互不相同。

以數組形式返回選擇的方案作為答案 answer，其中 answer[i] 為在第 (i+1) 個花園中種植的花的種類。花的種類用 1, 2, 3, 4 表示。保證存在答案。

示例 1： 輸入：N = 3, paths = [[1,2],[2,3],[3,1]] 輸出：[1,2,3]示例 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 <= 10000 0 <= paths.size <= 20000 不存在花園有 4 條或者更多路徑可以進入或離開。 保證存在答案。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/flower-planting-with-no-adjacent
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 圖的表示方法

參考圖的數據結構

• 建立鄰接表
• 遍歷每個節點的鄰接表，將鄰接表中出現的花刪除，若該節點每種，就在剩余的里選一個種上

class Solution { public:vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {vector<vector<int>> adj(N+1);//圖有N個節點for(int i = 0; i < paths.size(); ++i){adj[paths[i][0]].push_back(paths[i][1]);//將一條邊加入圖adj[paths[i][1]].push_back(paths[i][0]);}unordered_set<int> flowers;vector<int> Node(N,-1);int i, j;for(i = 1; i <= N; ++i)//遍歷N個鄰接鏈{flowers = {1,2,3,4};//可種花的種類for(j = 0; j < adj[i].size(); ++j)//相鄰的都種了花了嗎？if(Node[adj[i][j]-1] != -1)flowers.erase(Node[adj[i][j]-1]);//種了，刪除，這種花不能種了if(Node[i-1] == -1)//沒有種植，在剩下的花里選一個，選beginNode[i-1] = *flowers.begin();}return Node;} };

總結

以上是生活随笔為你收集整理的LeetCode 1042. 不邻接植花（图的数据结构）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。