P6279 [USACO20OPEN] Favorite Colors G
题目描述
Farmer John 的 $N$ 头奶牛每头都有一种最喜欢的颜色。奶牛们的编号为 $1\ldots N$，每种颜色也可以用 $1\ldots N$ 中的一个整数表示。
存在 $M$ 对奶牛 $(a,b)$，奶牛 $b$ 仰慕奶牛 $a$。有可能 $a=b$，此时一头奶牛仰慕她自己。对于任意颜色 $c$，如果奶牛 $x$ 和 $y$ 都仰慕一头喜欢颜色 $c$ 的奶牛，那么 $x$ 和 $y$ 喜欢的颜色相同。
给定这些信息，求一种奶牛喜欢颜色的分配方案，使得每头奶牛最喜欢的颜色中不同颜色的数量最大。由于存在多种符合这一性质的分配方案，输出字典序最小的（这意味着你应当依次最小化分配给奶牛 $1 \ldots N$ 的颜色）。
输入格式
无
输出格式
无
说明/提示
#### 样例解释：
在下图中，用粗边框圆表示的是最喜欢颜色 $1$ 的奶牛。
-----
对于 $100\%$ 的数据，$1\le N,M\le 2\times 10^5$。
共 $10$ 个测试点，其中 $1$ 为样例，其余性质如下：
测试点 $2\sim 3$ 满足 $N,M\le 10^3$。
测试点 $4\sim 10$ 没有额外限制。
-----
出题人：William Lin，Benjamin Qi