Graph Coloring

题目描述

给定一个包含 $n$ 个节点和 $m$ 条边的简单图。你的任务是使用尽可能少的颜色为每个节点着色，使得没有一条边连接两个相同颜色的节点。

输入格式

第一行有两个整数 $n$ 和 $m$：节点数和边数。节点编号为 1, 2,$\dots$, $n$。 接下来的 $m$ 行描述边。每行有两个整数 $a$ 和 $b$：表示存在一条连接节点 $a$ 和 $b$ 的边。

输出格式

首先，输出一个整数 $k$：最少所需的颜色数。 之后输出 $n$ 个整数 $c_1, c_2,$$\dots,$$c_n$：各节点的颜色。颜色应满足 $1 \le c_i \le k$。 你可以输出任意一个合法的解。

4 4
1 2
2 3
3 4
4 1

2
1 2 1 2

提示

$1 \le n \le 16$ $0 \le m \le \frac{n(n-1)}{2}$

标签: CSES3308|高级图论问题

来源

CSES3308|高级图论问题