Planets and Kingdoms

题目描述

一个游戏有 $n$ 个行星，由 $m$ 个传送门相连。当且仅当存在一条从行星 $a$ 到行星 $b$ 的路径且存在一条从行星 $b$ 到行星 $a$ 的路径时，行星 $a$ 和 $b$ 属于同一个王国。你的任务是确定每个行星所属的王国。

输入格式

第一行输入包含两个整数 $n$ 和 $m$：行星数和传送门数。行星编号为 1,2,$\dots$, $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

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1683|图论

来源

CSES1683|图论