Pro.ID1572 Title割边(桥) Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1572 AC9 Submit41 Ratio21.95% 时间&空间限制描述在无向连通图G中,如果删除某一条边e=(u, v),连通分量数目增加,称e为图的 割边,也称为 桥 。 现给出一个无向连通图,请找出它的所有桥。 输入多测试用例。 每个测试用例的第一行是两个正整数n和e ( 0 < n < 1000, 0 < e < 200000 ),分别表示这个无向图的顶点总数(顶点编号从0到n-1),边的总数。测试数据不出现重边,不出现自环。 接下来e行,每行两个非负整数a, b ( 0 ≤ a, b ≤ n-1 ),表示一条顶点a到顶点b的边。 输出Description 在无向连通图G中,如果删除某一条边e=(u, v),连通分量数目增加,称e为图的 割边,也称为 桥 。 现给出一个无向连通图,请找出它的所有桥。 Input 多测试用例。 每个测试用例的第一行是两个正整数n和e ( 0 < n < 1000, 0 < e < 200000 ),分别表示这个无向图的顶点总数(顶点编号从0到n-1),边的总数。测试数据不出现重边,不出现自环。 接下来e行,每行两个非负整数a, b ( 0 ≤ a, b ≤ n-1 ),表示一条顶点a到顶点b的边。 Output 请为每个测试用例输出: 第一行,一个非负整数c,表示桥的数量。 第二行至第c +1行,输出桥的两个端点的编号。如果c=0,这一部分省略。每一条桥(u, v)的两个顶点,编号较小的顶点为u,编号较大的为v。输出时按顶点u编号,从小到大输出,u相同时,按v编号从小到大输出。 最后一行,空行。仅起分隔作用。 Sample Input 6 7 Sample Output 1 Hint 样例1如下图 样例2如下图 Author 样例输入6 7 样例输出1 提示样例1如下图 样例2如下图 作者 |