请教两个题目
本帖最后由 suntot 于 2013-01-15 22:25:06 编辑 第一题
已知计算机有以下原子操作
1、 赋值操作：b = a;
2、 ++a和a+1;
3、for( ){ ***}有限循环；
4、操作数只能为0或者正整数；
5、定义函数
实现加减乘操作

第二题
平面上有很多点，点与点之间有可能有连线，求这个图里环的数目

多谢指教
[解决办法]
对于第二题，我觉得可以这么做：
对于图上的每个点，标记三种状态：A：未找到经过该点的环，B：已经找到经过该点的环，C：未访问到该点，D：该点访问过1次，E：该点访问过2次或以上。
初始情况，每个点都是A以及C状态。
首先，以某个点如v1为起点进行宽度优先遍历，当访问到任意一点如v2有以下三种情况：
1.若v2状态未C，则v2状态改为D；
2.若v2状态为D，状态改为E，把v1状态变为B，v1经过的环数加1，同时访问到v2的这条路线终止
3.若v2状态为E，访问到v2的这条路线终止。
遍历完，则找到所有v1参与的环的数目。这个过程为O(n)。
然后，则以另一个点如v3为起点，遍历整张图，这时需要把先每个点状态恢复为C。这里遍历就要加一个限制，若访问到状态为B的点，这条路线终止，因为状态为B的点参与的所有环已经在前面的步骤中找到。这样就可以找到v3参与的但与前面的环不重复的环的数目。
因此总的复杂度为O(n^2)，不知道有没有更优的办法。