# 1042.Flower Planting with no Adjacent

**1042.Flower Planting with no Adjacent**

难度:Easy

> 有 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 条或者更多路径可以进入或离开。
保证存在答案。
```

本质上是四色问题的染色，使用回溯法。

```
class Solution {
private:
    int n,m;
    int color[10000];
    vector<vector<int>>a;
    bool Valid(int t)
    {
        if(a[t].size()<1) return true;
        for(auto i:a[t])
            if(color[t]==color[i])
                return false;  
        return true;
    }
    bool traceback(int t)
    {
       //cout<<t<<endl;
        if(t==n) return true;
        for(int i=1;i<=m;i++)
        {
            color[t]=i;
            if(Valid(t))
            {
                if(traceback(t+1)) return true;
            }
        }
        return false;
    }
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        n=N;
        m=4;
        vector<int> tmp{-1};
        a.resize(10000);
        for(int i=0;i<paths.size();i++)
        {
            a[paths[i][0]-1].push_back(paths[i][1]-1);
            a[paths[i][1]-1].push_back(paths[i][0]-1);
        }
        traceback(0);
        vector<int >answer(color,color+N);
        return answer;
    }
};
```

著名的NP完全问题，难度分类不应该是EASY，回溯法是暴力解法。

> 执行用时 : 232 ms, 在Flower Planting With No Adjacent的C++提交中击败了92.48% 的用户 内存消耗 : 49.9 MB, 在Flower Planting With No Adjacent的C++提交中击败了100.00% 的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/1042.flower_planting_with_no_adjacent.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.