Pro.ID1571 Title关节点(割点) Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1571 AC16 Submit119 Ratio13.45% 时间&空间限制描述在无向连通图G中,当且仅当删去G中的 顶点v 及 依附于v的所有边后,可将图分割成两个或两个以上的连通分量,则称顶点v为 关节点articulation point ,也称为 割点 。 没有关节点的连通图叫做 重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。 现给出一个无向连通图,请找出它的所有关节点。 输入多测试用例。 每个测试用例的第一行是两个正整数n和e ( 0 < n < 1000, 0 < e < 200000 ),分别表示这个无向图的顶点总数(顶点编号从0到n-1),边的总数。测试数据不出现重边,不出现自环。 接下来e行,每行两个非负整数a, b ( 0 ≤ a, b ≤ n-1 ),表示一条顶点a到顶点b的边。 输出Description 在无向连通图G中,当且仅当删去G中的 顶点v 及 依附于v的所有边后,可将图分割成两个或两个以上的连通分量,则称顶点v为 关节点articulation point ,也称为 割点 。 没有关节点的连通图叫做 重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。 现给出一个无向连通图,请找出它的所有关节点。 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个关节点的编号。每个编号后面跟一个空格。如果c=0,本行省略。 第三行,空行。仅起分隔作用。 Sample Input 6 7 Sample Output 2 Hint 样例1如下图 样例2如下图 Author 样例输入6 7 样例输出2 提示样例1如下图 样例2如下图 作者 |