Dotcpp  >  编程题库  >  数据结构-关节点和重连通分量
题目 1706:

数据结构-关节点和重连通分量

时间限制: 3s 内存限制: 96MB 提交: 165 解决: 12

题目描述

假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连接分量,则称顶点v为该图的一个关节点。一个没有关节点的连通图称为重连通图。在重连通图上,任意一对顶点之间至少存在两条路径,则在删去某个顶点以及依附于该顶点的各边时也不会破坏图的连通性。
利用深度优先搜索可以求出图的关节点,并由此可以判断图是否是重连通的。
通过修改深度优先搜索遍历的算法便可以得到求关节点的算法,其算法描述如下:
关节点和重连通分量
关节点和重连通分量2
在本题中,读入一个无向图的邻接矩阵(即数组表示),建立无向图并按照以上描述中的算法求出所有的关节点,并输出这些关节点。

输入格式

输入的第一行包含一个正整数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 

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签

通过率

统 计