#N2U13P01. 关键道路编号
关键道路编号
关键道路编号
难度:T4
【知识点:割点与割边】
前置知识:割点与割边及其冻结前置单元。
题目描述与输入
第一行 ,随后行无向边 ,。找出所有桥。
规则说明
桥是这样的一条边:只删除这一条边后,整个图的连通分量数会增加。连通分量是尽可能大的一组相互可达的顶点,孤立点也算一个分量。重边须按各自编号区分;删除一条边不会同时删除其他相同端点的边。
输出
第一行输出数量;第二行按编号升序输出输入边编号,无则第二行为空。
数据范围
,,。无向多重图,桥按输入边编号到识别。
样例输入
4 4
1 2 1
2 3 1
3 1 1
3 4 1
样例输出
1
4
样例说明
前三条边在环内,只有第条—是桥。