这是一道模板题。边双连通分量(极大边双连通子图)是没有桥的连通图。
给定一张带边权的无向图,定义边双连通分量的边权是它所有边的边权里最小的边权(特别地,无边的分量认为是最小的),请输出边双连通分量数目并按照边双连通分量边权升序输出每个分量的每条边,分量内的边权也按升序输出。
输入
输入一行两个整数 n,m(2\le n\le10^5,1\le m\le 10^5),代表图的点数和边数。
接下来输入 m 行,每行三个整数 u,v,w(1\le u,v\le n,u\neq v,-10^9\le w\le10^9),代表无向边 (u,v),边权为 w。保证每条边边权互不相同,且保证输入的图为简单连通图。
输出
输出一行一个整数 s 代表边双连通分量数。
接下来输出 s 行,第 i 行首先输出一个整数 t 代表第 i 个双连通分量的边数,接下来同一行内输出 t 个整数,代表第 i 个边双连通分量每条边的边权。
样例
标准输入 复制文本 |
4 6 1 2 1 1 3 2 1 4 3 2 3 4 2 4 5 3 4 6 |
标准输出 复制文本 |
1 6 1 2 3 4 5 6 |
标准输入 复制文本 |
8 9 1 2 1 2 3 3 3 1 2 2 4 0 4 5 4 5 6 5 6 7 6 7 8 7 8 4 8 |
标准输出 复制文本 |
2 3 1 2 3 5 4 5 6 7 8 |
标准输入 复制文本 |
4 3 1 2 -1 2 3 -2 3 4 -3 |
标准输出 复制文本 |
4 0 0 0 0 |