CSES - 不同颜色

以下是一个解决CSES问题的示例代码：

def color_graph(graph, colors, node):
    # 获取当前节点的邻居节点
    neighbors = graph[node]
    # 获取当前节点已经被分配的颜色
    current_color = colors[node]
    # 遍历邻居节点
    for neighbor in neighbors:
        # 如果邻居节点还没有被分配颜色，则尝试分配一个不同的颜色
        if colors[neighbor] == 0:
            for color in range(1, len(colors)+1):
                if color != current_color:
                    colors[neighbor] = color
                    break
            # 递归调用对邻居节点进行着色
            color_graph(graph, colors, neighbor)

使用示例代码，我们可以通过以下方式调用它来解决CSES问题：

# 输入图的节点数量和边的数量
n, m = map(int, input().split())
# 创建一个空的邻接列表来表示图
graph = [[] for _ in range(n+1)]
# 创建一个空的颜色列表，初始都为0，表示未分配颜色
colors = [0] * (n+1)

# 输入边的信息并构建图的邻接列表
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 对每个节点进行着色
for node in range(1, n+1):
    # 如果当前节点还没有被分配颜色，则从颜色1开始尝试
    if colors[node] == 0:
        colors[node] = 1
        color_graph(graph, colors, node)

# 输出每个节点的颜色
for i in range(1, n+1):
    print(colors[i], end=" ")
print()

这个示例代码使用了深度优先搜索（DFS）的算法来为图中的节点着色。首先，它会构建图的邻接列表表示，然后从每个节点开始进行着色。对于每个节点，它会检查邻居节点是否已经被分配了颜色，如果没有，它会尝试为邻居节点分配一个不同的颜色。然后，它会递归调用color_graph函数继续为邻居节点进行着色。最后，它会输出每个节点的颜色。

希望这个示例代码能够帮助你解决CSES问题！