1571_关节点(割点)

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

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

Pro.ID

1571

Title

关节点(割点)

Title链接

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

AC

16

Submit

119

Ratio

13.45%

时间&空间限制

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

    在无向连通图G中,当且仅当删去G中的 顶点v 及 依附于v的所有边后,可将图分割成两个或两个以上的连通分量,则称顶点v关节点articulation point ,也称为 割点

    没有关节点的连通图叫做 重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。

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

    输入

    多测试用例。

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

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

    输出

    Description

    在无向连通图G中,当且仅当删去G中的 顶点v 及 依附于v的所有边后,可将图分割成两个或两个以上的连通分量,则称顶点v关节点articulation point ,也称为 割点

    没有关节点的连通图叫做 重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。

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

    Input

    多测试用例。

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

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

    Output

    请为每个测试用例输出:

    第一行,一个非负整数c,表示关节点的数量。

    第二行,从小到大输出c个关节点的编号。每个编号后面跟一个空格。如果c=0,本行省略。

    第三行,空行。仅起分隔作用。

    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

    2
    2 3

    1
    2

    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

    样例输出

    2
    2 3

    1
    2

    提示

    样例1如下图

    样例2如下图

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部