本题关联比赛
csp2025模拟练习1

关于彩色道路的近10条评论(全部评论)

4183. 彩色道路

★★☆ 输入文件：paintoads.in 输出文件：paintoads.out 评测插件
时间限制：1 s 内存限制：512 MiB

K 市的市长老A 成功地改进了该市的道路规划。然而，来自 R 市的一位售货员仍然抱怨道路的颜色不够丰富。老A 的下一个任务就是粉刷一些道路。

K 市的道路规划可以表示为 $N$ 个十字路口和 $M$ 条道路，第 $i$ 条道路连接第 $u_{i}$ 个十字路口和第 $v_{i}$ 个十字路口。一开始所有道路都是灰色的。老A 想要把一些道路染成红色或者蓝色，满足以下条件：

对于每一条灰色道路，假设其连接十字路口 $u_{i}$ 和十字路口 $v_{i}$ ，一定存在一条从十字路口 $u_{i}$ 到十字路口 $v_{i}$ 的路径，满足路径上的道路颜色红色和蓝色交替出现，任何道路都不是灰色的。

为了降低城市的支出，老A 希望尽可能少地对道路进行染色。请帮助 K 市设计一个符合要求的染色方案。

输入的第一行包含两个整数 $N$ 和 $M$ （ $1 \leq N, M \leq 2 \times 1 0^5$ ）。

接下来 $M$ 行中的第 $i$ 行包含两个整数 $u_{i}$ 和 $v_{i}$ 表示存在一条连接十字路口 $u_{i}$ 和十字路口 $v_{i}$ 的道路（ $1 \leq u_{i}, v_{i} \leq N$ ， $u_{i}!= v_{i}$ ）。

任意两个十字路口之间至多存在一条道路。

输出一个长度为 $M$ 的字符串，表示染色的方案。第 $i$ 个字符表示第 $i$ 条道路的颜色，R 表示红色，B 表示蓝色，G 表示灰色（未染色）。

注意你必须在满足条件的情况下最小化染色的道路数目。如果存在多个这样的染色方案，输出任意一个。

BRGBBGG

4 2
1 2
3 4

BB

【样例 1 解释】

十字路口以及有效的道路的示意图如下所示，该方案最小化了染色道路的数量。请注意，每条道路上的颜色显示为 R（红色）、B（蓝色）或 G（灰色）。

所有为染色的道路都满足条件：

【样例 2 解释】

请注意 Kitchener 的道路可能不是连通的。

对于所有数据，保证 $1 \leq N, M \leq 2 \times 1 0^5$ ， $1 \leq u_{i}, v_{i} \leq N$ ， $u_{i \neq} v_{i}$

测试点	附加条件
$1-10$	对任意 $1 \leq i < N$ 存在一条连接 $i$ 和 $i + 1$ 的道路（还可能存在其他道路）
$11-20$	图连通并且 $N = M$
21-34	任何道路都不同时属于至少两个简单环（见下文定义）
$35-50$	无

定义：若用

u \leftrightarrow v

表示一条连接

u

和

v

的道路，则称

k \geq 3

且所有

w_{i}

互不相同时，序列

w_{1} \leftrightarrow w_{2} \leftrightarrow \dots \leftrightarrow w_{k} \leftrightarrow w_{1}

为简单环。

在此键入。