Problem 2085 --算法7-10,7-11:关节点和重连通分量

2085: 算法7-10,7-11:关节点和重连通分量

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $21$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 递归 搜索 图论
假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连接分量,则称顶点v为该图的一个关节点。一个没有关节点的连通图称为重连通图。在重连通图上,任意一对顶点之间至少存在两条路径,则在删去某个顶点以及依附于该顶点的各边时也不会破坏图的连通性。
利用深度优先搜索可以求出图的关节点,并由此可以判断图是否是重连通的。
通过修改深度优先搜索遍历的算法便可以得到求关节点的算法,其算法描述如下:

在本题中,读入一个无向图的邻接矩阵(即数组表示),建立无向图并按照以上描述中的算法求出所有的关节点,并输出这些关节点。

输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1,对于第i行的第j个整数,如果为1,则表示第i个顶点和第j个顶点有直接连接,0表示没有直接连接。当i和j相等的时候,保证对应的整数为0。
输入保证邻接矩阵为对称矩阵,即输入的图一定是无向图,且保证图中只有一个连通分量。
第一行有一个整数x,即图中关节点的个数。
第二行输出x个整数,表示所有关节点的顶点编号,请按照编号从小到大的顺序输出。每个整数后输出一个空格,并请注意行尾输出换行。
4
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
1
0 
在本题中,需要掌握图的深度优先遍历的方法,并需要掌握通过深度优先搜索求得图中关节点的算法。通过生成深度优先生成树可以得出两类关节点的特性:
1.       若生成树的根有两棵或两棵以上的子树,则此根顶点必为关节点。
2.       若生成树中某个非叶子顶点v,其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边,则说明v是关节点。
注意以上两点特性,就可以成功的通过深度优先搜索遍历的算法得出图中的关节点了。

推荐代码 查看2085 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 范晋豪@信息与计算科学142 152733 2017-11-16 15:10:16
内存最少[$948 $KB] 范晋豪@信息与计算科学142 152733 2017-11-16 15:10:16
第一AC 范晋豪@信息与计算科学142 152733 2017-11-16 15:10:16
第一挑战 范晋豪@信息与计算科学142 152733 2017-11-16 15:10:16

赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记

竞赛编号 竞赛名称 竞赛时间 访问比赛
1149 2017-2018-2《C语言程序设计II》课下练习@2017计算机科学与技术123 2018-03-06 12:00:00 请登录