#L0003. 无向图的块划分

无向图的块划分

题目背景

图论研修课上,同学们刚学完「割点」与「块」的概念。为了检验大家的掌握程度,助教布置了下面这道巩固练习。

题目描述

现给出一张含 nn 个顶点、mm 条边的无向图,顶点编号依次为 11nn。图中可能含有重边与自环,也未必连通。请你找出这张图的全部「块」。

约定:不与任何边关联的顶点不算作割点,因此仅由一个孤立顶点构成的连通块也不视为块。可以结合样例体会这一约定。

输出时需遵守统一的顺序:对每个块,块内顶点按编号从小到大排列;对任意两个块,把各自包含的顶点依次取出排成序列,字典序较小的块排在前面。所有块均按此顺序输出。

输入格式

第一行两个正整数 nnmm,依次表示顶点数与边数。

随后 mm 行,每行两个正整数 uuvv,表示一条连接顶点 uu 与顶点 vv 的无向边。

输出格式

第一行输出一个整数 CntCnt,即图中块的个数。

接下来 CntCnt 行,第 ii 行输出第 ii 个块包含的全部顶点;同一块内顶点编号按从小到大的顺序输出,各块之间按题目约定的字典序排列。

样例

7 7
5 6
1 2
3 5
1 4
3 1
4 5
2 5
2

1 2 3 4 5 5 6

</p>

提示

本题不设部分分。

对于全部数据,保证 1n500001\leq n \leq 500001m3000001 \leq m \leq 300000,输入的图合法且满足上述限制。

难度 普及+/提高-
通过率
尝试 0
已通过 0
ID
731
类型
传统题
Time Limit
1000ms
Memory Limit
512MiB
上传者