Medium

题目描述

你有 n 个花园，标号从 1 到 n，还有一个数组 paths，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。

所有花园最多有 3 条路径可以进入或离开。

你需要为每个花园选择一种花的类型，使得通过路径连接的任何两个花园都拥有不同类型的花。

以数组形式返回 任一 可行的方案作为答案，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^4
  • 0 <= paths.length <= 2 * 10^4
  • paths[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • 每个花园最多有 3 条路径可以进入或离开

解题思路

这是一个图着色问题的简化版本。核心思路是利用贪心算法和图的性质来解决。

关键观察：

  1. 每个花园最多连接3个其他花园
  2. 我们有4种颜色可选
  3. 根据鸽笼原理，对于任意一个花园，即使它的3个邻居都已着色，我们仍然有至少1种颜色可用

解法分析：

方法一：贪心着色（推荐）

  • 构建邻接表表示图
  • 按顺序遍历每个花园，为每个花园选择一个与邻居不同的颜色
  • 对于当前花园，检查已着色邻居使用的颜色，选择第一个未被使用的颜色

方法二：DFS/BFS着色

  • 类似方法一，但使用深度优先搜索或广度优先搜索的顺序来着色
  • 由于图可能不连通，需要处理多个连通分量

算法步骤：

  1. 根据paths构建邻接表
  2. 初始化结果数组，所有花园初始颜色为0（未着色）
  3. 遍历每个花园，对于当前花园，检查其邻居的颜色，选择第一个可用颜色（1-4）

时间复杂度为O(n + m)，空间复杂度为O(n + m)，其中m是边数。

代码实现

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> graph(n + 1);
        
        // 构建邻接表
        for (auto& path : paths) {
            graph[path[0]].push_back(path[1]);
            graph[path[1]].push_back(path[0]);
        }
        
        vector<int> result(n, 0);
        
        // 为每个花园选择颜色
        for (int i = 1; i <= n; i++) {
            vector<bool> used(5, false); // 颜色1-4的使用情况
            
            // 检查邻居使用的颜色
            for (int neighbor : graph[i]) {
                if (result[neighbor - 1] != 0) {
                    used[result[neighbor - 1]] = true;
                }
            }
            
            // 选择第一个可用的颜色
            for (int color = 1; color <= 4; color++) {
                if (!used[color]) {
                    result[i - 1] = color;
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        # 构建邻接表
        graph = [[] for _ in range(n + 1)]
        for x, y in paths:
            graph[x].append(y)
            graph[y].append(x)
        
        result = [0] * n
        
        # 为每个花园选择颜色
        for i in range(1, n + 1):
            used = [False] * 5  # 颜色1-4的使用情况
            
            # 检查邻居使用的颜色
            for neighbor in graph[i]:
                if result[neighbor - 1] != 0:
                    used[result[neighbor - 1]] = True
            
            # 选择第一个可用的颜色
            for color in range(1, 5):
                if not used[color]:
                    result[i - 1] = color
                    break
        
        return result

public class Solution {
    public int[] GardenNoAdj(int n, int[][] paths) {
        // 构建邻接表
        List<int>[] graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var path in paths) {
            graph[path[0]].Add(path[1]);
            graph[path[1]].Add(path[0]);
        }
        
        int[] result = new int[n];
        
        // 为每个花园选择颜色
        for (int i = 1; i <= n; i++) {
            bool[] used = new bool[5]; // 颜色1-4的使用情况
            
            // 检查邻居使用的颜色
            foreach (int neighbor in graph[i]) {
                if (result[neighbor - 1] != 0) {
                    used[result[neighbor - 1]] = true;
                }
            }
            
            // 选择第一个可用的颜色
            for (int color = 1; color <= 4; color++) {
                if (!used[color]) {
                    result[i - 1] = color;
                    break;
                }
            }
        }
        
        return result;
    }
}

var gardenNoAdj = function(n, paths) {
    // 构建邻接表
    const graph = Array.from({length: n + 1}, () => []);
    for (const [x, y] of paths) {
        graph[x].push(y);
        graph[y].push(x);
    }
    
    const result = new Array(n).fill(0);
    
    // 为每个花园选择颜色
    for (let i = 1; i <= n; i++) {
        const used = new Array(5).fill(false); // 颜色1-4的使用情况
        
        // 检查邻居使用的颜色
        for (const neighbor of graph[i]) {
            if (result[neighbor - 1] !== 0) {
                used[result[neighbor - 1]] = true;
            }
        }
        
        // 选择第一个可用的颜色
        for (let color = 1; color <= 4; color++) {
            if (!used[color]) {
                result[i - 1] = color;
                break;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)其中 n 是花园数量，m 是路径数量。需要遍历所有花园和路径
空间复杂度O(n + m)邻接表存储图的空间复杂度，以及结果数组的空间