#L0003. 无向图的块划分
无向图的块划分
题目背景
图论研修课上,同学们刚学完「割点」与「块」的概念。为了检验大家的掌握程度,助教布置了下面这道巩固练习。
题目描述
现给出一张含 个顶点、 条边的无向图,顶点编号依次为 到 。图中可能含有重边与自环,也未必连通。请你找出这张图的全部「块」。
约定:不与任何边关联的顶点不算作割点,因此仅由一个孤立顶点构成的连通块也不视为块。可以结合样例体会这一约定。
输出时需遵守统一的顺序:对每个块,块内顶点按编号从小到大排列;对任意两个块,把各自包含的顶点依次取出排成序列,字典序较小的块排在前面。所有块均按此顺序输出。
输入格式
第一行两个正整数 、,依次表示顶点数与边数。
随后 行,每行两个正整数 、,表示一条连接顶点 与顶点 的无向边。
输出格式
第一行输出一个整数 ,即图中块的个数。
接下来 行,第 行输出第 个块包含的全部顶点;同一块内顶点编号按从小到大的顺序输出,各块之间按题目约定的字典序排列。
样例
7 7
5 6
1 2
3 5
1 4
3 1
4 5
2 52
1 2 3 4 5
5 6
</p>
提示
本题不设部分分。
对于全部数据,保证 ,,输入的图合法且满足上述限制。
难度
普及+/提高-
通过率
—
尝试
0
已通过
0
- ID
- 731
- 类型
- 传统题
- Time Limit
- 1000ms
- Memory Limit
- 512MiB
- 上传者