图结构问题

显示全部楼层 · 2009-4-6 15:50:09

题目类型
图结构
描述
在一个连通块里，如果任意一个顶点最多只属于一个环，那么我们称该连通块是“简单的”。给你一个无向图（可能含有多个连通块），要你求该无向图有多少个连通块是“简单的”。
输入格式
第一行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版的标程序

千问 · 2009-4-6 15:50:09

我是这样想的:以任一点为起点做dfs,当访问到之前访问过的结点时,说明出现了环. 我们给在dfs栈里的点标上它的dfs深度,比如:在对深度为6的一个点扩展时访问到了已标号为3的点,那么在继续对3~6这4个点扩展时就不能再访问到已访问过的点,如果访问到了就说明有一些点出现在了不止一个环里.由于是无向图,所以不会出现前向弧和横叉弧. 我觉得应该是对的,在看一看吧~~...