#N2U14P01. 去桥后的分块大小
去桥后的分块大小
去桥后的分块大小
难度:T4
【知识点:双连通分量】
前置知识:双连通分量及其冻结前置单元。
题目描述与输入
第一行 ,随后行无向边 。删去所有桥,输出剩下各连通块的顶点个数。
规则说明
桥是这样的一条边:只删除这一条边后,整个图的连通分量数会增加。连通分量是尽可能大的一组相互可达的顶点,孤立点也算一个分量。重边须按各自编号区分;删除一条边不会同时删除其他相同端点的边。
输出
第一行块数;第二行将各块大小从小到大输出。
数据范围
,,,无向图,无自环,允许平行边。
样例输入
5 6
1 2 1
2 3 1
3 1 1
3 4 1
4 5 1
5 3 1
样例输出
1
5
样例说明
共点两环没有桥,去桥后仍是一个大小的块。