B3610 [图论与代数结构 801] 无向图的块
题目描述
在离散数学课程的学习中,大家学习了无向图中”割点“和“块”的定义,现在来检查一下大家的学习情况。
给定一张 $n$ 个点 $m$ 条边的无向图,点的编号从 $1$ 到 $n$ ,可能存在重边和自环,不保证是一张连通图。现在,请你求出这张图所有的块。
注意,我们不把一个没有任何与其相连边的点看成割点;因此,一个单独的点构成的连通块不被看成是块。你可以通过样例理解这个事情。
在输出的时候,我们规定这么一个输出的顺序:首先,对于一个块,我们把该块中所有点按照编号从小到大排序;然后,对于两个块,我们规定,把点按照顺序拿出来排成一个序列,字典序较小的排在前面。这样,我们就可以对所有块规定了一个顺序。最终输出就按照这样的顺序输出。
有关字典序的定义,可以在搜索引擎上查找,或者参考[维基百科_字典序](https://en.wikipedia.org/wiki/Lexicographic_order)。
输入格式
第一行两个正整数 $n$ 和 $m$ ,分别表示给定无向图的点数和边数。
接下来 $m$ 行,每行两个正整数 $u$ 和 $v$ 表示一条连接这两个点的无向边。
输出格式
第一行一个正整数 $Cnt$ 表示答案,即图中块的个数。
接下来 $Cnt$ 行,第 $i$ 行输出若干个正整数,表示第 $i$ 个块中的所有点。注意同一个块点的编号按照从小到大的顺序输出。按照题目中规定的字典序顺序输出块。
说明/提示
本题没有部分分。
对于所有数据,满足 $1\leq n \leq 50000$,$1 \leq m \leq 300000$,保证输入的图合法且满足题目中的限制条件。