CSES1683 行星与王国
#CS1683. 行星与王国
行星与王国
题目背景
翻译自 CSES-1683 题。
题目描述
一个游戏中有 n 个行星，通过 m 条传送门连接。两个行星 a 和 b 属于同一个王国，当且仅当存在一条路径从 a 到 b 且从 b 到 a。你的任务是确定每个行星所属的王国。
输入格式
第一行包含两个整数 n 和 m：分别表示行星的数量和传送门的数量。行星编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来有 m 行，每行包含两个整数 a 和 b：表示从行星 a 可以通过传送门到达行星 b。
输出格式
首先输出一个整数 k：表示王国的数量。
然后，对于每个行星，输出一个王国标签，标签范围在 1 到 k 之间。你可以输出任何有效的解。
样例
5 6
1 2
2 3
3 1
3 4
4 5
5 4
2
1 1 1 2 2
说明/提示