<jupyter_start><jupyter_text>有 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^4    0 <= paths.length <= 2 * 10^4    paths[i].length == 2    1 <= xi, yi <= n    xi != yi    每个花园 最多 有 3 条路径可以进入或离开<jupyter_code>from collections import defaultdict

class Solution:
    def gardenNoAdj(self, n: int, paths):
        graph = defaultdict(set)
        for a, b in paths:
            graph[a].add(b)
            graph[b].add(a)
        
        res = [0] * (n+1)
        for i in range(1, n+1):
            path_colors = set() # 存储了与 i 相连的路径可以种哪些花
            for j in graph[i]: # 与 i 相连的路径
                path_colors.add(res[j])
                
            for color in range(1, 5):
                if color not in path_colors: # 如果想要种的花不在 其他路径种，那么就是可以种的
                    res[i] = color
                    break
        return res[1:]
solution = Solution()
solution.gardenNoAdj(n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16774611398963732, 'fraction_numerical': 0.06217616580310881, 'mean_word_length': 2.212058212058212, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '140111', 'license': 'Apache-2.0', 'n_tokens_mistral': 869, 'n_tokens_neox': 909, 'n_words': 158, 'path': 'Graph/1114/1042. Flower Planting With No Adjacent.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '1544'}