UC知道图结构问题
来源：百度知道 编辑：UC知道 时间：2024/06/17 03:12:31
题目类型
图结构
描述
在一个连通块里，如果任意一个顶点最多只属于一个环，那么我们称该连通块是“简单的”。 给你一个无向图（可能含有多个连通块），要你求该无向图有多少个连通块是“简单的”。
输入格式
第一行N 和 M ,其中N表示无向图的顶点数， M表示无向图的边数。1≤N≤300,0≤M≤30000.
接下来有M行， 每行两个整数a, b. 表示a 到 b之间有一条边。
输出格式
一个数
样例输入
3 3
1 2
1 3
2 3
样例输出
1
一定要有解题思路，其中最重要是如何判断一个连同块里面的定点只在一个环内~~~
最好要有PASCAL版的标程序
图结构
描述
在一个连通块里，如果任意一个顶点最多只属于一个环，那么我们称该连通块是“简单的”。 给你一个无向图（可能含有多个连通块），要你求该无向图有多少个连通块是“简单的”。
输入格式
第一行N 和 M ,其中N表示无向图的顶点数， M表示无向图的边数。1≤N≤300,0≤M≤30000.
接下来有M行， 每行两个整数a, b. 表示a 到 b之间有一条边。
输出格式
一个数
样例输入
3 3
1 2
1 3
2 3
样例输出
1
一定要有解题思路，其中最重要是如何判断一个连同块里面的定点只在一个环内~~~
最好要有PASCAL版的标程序
我是这样想的:以任一点为起点做dfs,当访问到之前访问过的结点时,说明出现了环. 我们给在dfs栈里的点标上它的dfs深度,比如:在对深度为6的一个点扩展时访问到了已标号为3的点,那么在继续对3~6这4个点扩展时就不能再访问到已访问过的点,如果访问到了就说明有一些点出现在了不止一个环里.
由于是无向图,所以不会出现前向弧和横叉弧.
我觉得应该是对的,在看一看吧~~