1572_割边(桥)

2022-5-16 18:17| 发布者: Hocassian| 查看: 48| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503982934899-Problem List-采集的数据-后羿采集器.html

Pro.ID

1572

Title

割边(桥)

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1572

AC

9

Submit

41

Ratio

21.95%

时间&空间限制

  • Time Limit: 2000/1000 MS (Java/Others)     Memory Limit: 65536/65536 K (Java/Others)
  • 描述

    在无向连通图G中,如果删除某一条边e=(u, v),连通分量数目增加,称e为图的 割边,也称为

    现给出一个无向连通图,请找出它的所有桥。

    输入

    多测试用例。

    每个测试用例的第一行是两个正整数ne ( 0 < n < 1000, 0 < e < 200000 ),分别表示这个无向图的顶点总数(顶点编号从0到n-1),边的总数。测试数据不出现重边,不出现自环。

    接下来e行,每行两个非负整数a, b ( 0 ≤ a, bn-1 ),表示一条顶点a到顶点b的边。

    输出

    Description

    在无向连通图G中,如果删除某一条边e=(u, v),连通分量数目增加,称e为图的 割边,也称为

    现给出一个无向连通图,请找出它的所有桥。

    Input

    多测试用例。

    每个测试用例的第一行是两个正整数ne ( 0 < n < 1000, 0 < e < 200000 ),分别表示这个无向图的顶点总数(顶点编号从0到n-1),边的总数。测试数据不出现重边,不出现自环。

    接下来e行,每行两个非负整数a, b ( 0 ≤ a, bn-1 ),表示一条顶点a到顶点b的边。

    Output

    请为每个测试用例输出:

    第一行,一个非负整数c,表示桥的数量。

    第二行至第c +1行,输出桥的两个端点的编号。如果c=0,这一部分省略。每一条桥(u, v)的两个顶点,编号较小的顶点为u,编号较大的为v。输出时按顶点u编号,从小到大输出,u相同时,按v编号从小到大输出。

    最后一行,空行。仅起分隔作用。

    Sample Input

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

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

    Sample Output

    1      
    2 3

    0

    Hint

    样例1如下图

    样例2如下图

    Author

    样例输入

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

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

    样例输出

    1      
    2 3

    0

    提示

    样例1如下图

    样例2如下图

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部