#L0140. 【模板】点双连通分量划分

【模板】点双连通分量划分

题目背景

星港联盟的通讯网由若干中继站与双向链路组成。工程部门排查隐患时发现,网络中存在一些「咽喉」中继站:它们一旦停机,整张网就会被劈成互不相通的几块——图论里把这样的节点称为割点,而把不含割点的子网称为点双连通子网。

点双连通分量的定义是极大的点双连通子图。不过「点双连通图」本身的口径在资料中并不统一:一种说法要求任意两个不同节点之间都有至少两条点不重复的路径,另一种说法要求图中不存在割点。两种口径在边界情形上略有出入,本题统一采用后者,即「不存在割点的图」。

题目描述

给你一个 nn 个节点、mm 条边的无向图,请统计它一共有多少个点双连通分量,并把每个点双连通分量分别包含哪些节点输出来。

输入格式

第一行两个整数 nnmm

接下来 mm 行,每行两个整数 u,vu, v,表示一条无向边。

输出格式

第一行输出一个整数 xx,表示点双连通分量的个数。

接下来 xx 行,每行先输出一个整数 aa 表示该分量的结点个数,再输出 aa 个整数,描述这个点双连通分量包含的结点。

你可以以任意顺序输出各个点双连通分量,也可以以任意顺序输出分量内部的结点。

样例

5 8
1 3
2 4
4 3
1 2
4 5
5 1
2 4
1 1
1

5 1 2 3 4 5

</p>
5 3
1 2
2 3
1 3
3

1 4 1 5 3 1 2 3

</p>
6 5
1 3
2 4
1 2
4 6
2 3
4

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

</p>
7 8
1 3
2 4
3 5
2 5
6 4
2 5
6 3
2 7
3

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

</p>
1 1
1 1
1

1 1

</p>

提示

温馨提示:请认真考虑孤立点与自环(样例五)的情况。

数据范围:
对于 100%100\% 的数据,1n5×1051 \le n \le 5 \times 10 ^ 51m2×1061 \le m \le 2 \times 10 ^ 6

subtask$n$$m$分值
$1$$1 \le n \le 100$$1 \le m \le 500$$25$
$2$$1 \le n \le 5000$$1 \le m \le 5 \times 10^4$$25$
$3$$1 \le n \le 2\times 10^5$$1 \le m \le 5\times 10^5$$25$
$4$$1 \le n \le 5 \times 10^5$$1 \le m \le 2 \times 10^6$$25$

本题不卡常,时间限制与空间限制均已开大,正确的解法均可通过。

本题答案不唯一,评测使用 Special Judge 校验输出是否合法。

难度 普及+/提高-
通过率 100%
尝试 1
已通过 1
ID
868
类型
传统题
Time Limit
5000ms
Memory Limit
500MiB
上传者