题目

标题和出处

标题：不邻接植花

出处：1042. 不邻接植花

难度

4 级

题目描述

要求

有 $\text{n}$ 个花园，从 $\text{1}$ 到 $\text{n}$ 编号，以及数组 $\text{paths}$，其中 ${\text{paths[i] = [x}}_{\text{i}}{\text{, y}}_{\text{i}}\text{]}$ 描述了花园 ${\text{x}}_{\text{i}}$ 到花园 ${\text{y}}_{\text{i}}$ 的双向路径。在每个花园中，你打算种下四种花之一。

所有花园最多有 $\text{3}$ 条路径可以进入或离开.

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回任一可行的方案作为答案 $\text{answer}$，其中 $\text{answer[i]}$ 为在第 $\text{i + 1}$ 个花园中种植的花的种类。花的种类用 $\text{1}$、$\text{2}$、$\text{3}$、$\text{4}$ 表示。保证存在答案。

示例

示例 1：

输入：$\text{n = 3, paths = [[1,2],[2,3],[3,1]]}$
输出：$\text{[1,2,3]}$
解释：
花园 $\text{1}$ 和 $\text{2}$ 花的种类不同。
花园 $\text{2}$ 和 $\text{3}$ 花的种类不同。
花园 $\text{3}$ 和 $\text{1}$ 花的种类不同。
因此，$\text{[1,2,3]}$ 是一个满足题意的答案。其他满足题意的答案有 $\text{[1,2,4]}$、$\text{[1,4,2]}$ 和 $\text{[3,2,1]}$。

示例 2：

输入：$\text{n = 4, paths = [[1,2],[3,4]]}$
输出：$\text{[1,2,1,2]}$

示例 3：

输入：$\text{n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]}$
输出：$\text{[1,2,3,4]}$

数据范围

• $\text{1}\le \text{n}\le {\text{10}}^{\text{4}}$
• $\text{0}\le \text{paths.length}\le \text{2}\times {\text{10}}^{\text{4}}$
• $\text{paths[i].length}=\text{2}$
• $\text{1}\le {\text{x}}_{\text{i}}{\text{, y}}_{\text{i}}\le \text{n}$
• ${\text{x}}_{\text{i}}\ne {\text{y}}_{\text{i}}$
• 每个花园最多有 $\text{3}$ 条路径可以进入或离开

解法

思路和算法

同一条路径连接的两个花园为相邻花园，则任意两个相邻花园中的花的种类互不相同。由于有 $4$ 种花，每个花园最多有 $3$ 个相邻的花园，因此一定存在答案。

为了确保相邻花园中的花的种类互不相同，需要遍历所有的路径，得到每个花园的相邻花园，然后按照编号从 $1$ 到 $n$ 的顺序依次遍历每个花园并决定每个花园中的花的种类。由于遍历花园的顺序是按照编号递增顺序，因此记录每个花园的相邻花园时只需要记录比当前花园的编号小的相邻花园。当遍历到一个花园时，比当前花园的编号小的所有花园都已经决定了花园中的花的种类。

遍历花园的过程中，对于每个花园，得到与当前花园相邻且编号比当前花园的编号小的全部花园，这些花园中的花的种类都已知，称为相邻花的种类。默认当前花园中的花的种类是 $1$，如果花的种类在相邻花的种类中出现，则将花的种类加 $1$，直到花的种类不在相邻花的种类中出现，则可确定当前花园中的花的种类。

遍历结束时，即可得到一个满足相邻花园中的花的种类互不相同的答案。

代码

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] adjacentGardens = new List[n];
        for (int i = 0; i < n; i++) {
            adjacentGardens[i] = new ArrayList<Integer>();
        }
        for (int[] path : paths) {
            int garden0 = path[0] - 1, garden1 = path[1] - 1;
            if (garden0 < garden1) {
                adjacentGardens[garden1].add(garden0);
            } else {
                adjacentGardens[garden0].add(garden1);
            }
        }
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            List<Integer> adjacent = adjacentGardens[i];
            boolean[] used = new boolean[5];
            for (int garden : adjacent) {
                int adjacentType = answer[garden];
                used[adjacentType] = true;
            }
            int type = 1;
            while (used[type]) {
                type++;
            }
            answer[i] = type;
        }
        return answer;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是花园数。需要遍历每条路径一次，得到每个花园的相邻花园，然后遍历每个花园一次，对于每个花园使用 $O(1)$ 的时间确定花的种类。由于每个花园最多和 $3$ 个花园相邻，因此路径数是 $O(n)$，确定一个花园中的花的种类的时间是 $O(1)$，时间复杂度是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是花园数。需要记录每个花园的相邻花园。