最重要的是在写之前多举几个刁钻的例子来理解问题和代码的正确性
如果你给不出反例就说明你还没有理解(有的反例会后来会被证明是错的)
由于递归是把自己的和别人的相关的混合在一起来了,所以举反例的时候要从不同的角度出发。
求割点的(关注割点和其他割点判断的关系)
等价是需要证明的,而不是想当然的以为然就可以的
就如下面这个求割点的
#include<stdio.h>
int index = 0,root;
int e[9][9],num[9],low[9],flag[9];
int n,m;int min(int x,int y){return x < y ? x : y;
}void dfs(int cur,int father){if(index == n)return;index ++;int i;num[cur] = index;low[cur] = num[cur];int child = 0;for(i = 1;i <= n;i ++){if(e[cur][i] == 1){child ++;if(num[i] == 0){dfs(i,cur);low[cur] = min(low[i],low[cur]); //给自己的父亲点用的点用的 //if(low[cur] >= num[cur] && cur != root) //wrong 因为这时在判断自己能不能过自己恒成立 if(low[i] >= num[cur] && cur != root) //自己作为父,让别人判断的 flag[cur] = 1;if(cur == root && child == 2)flag[cur] = 1;} //low是对于儿子而言说的 else if(i != father) //祖宗本来是要到这来的,顺序问题 不走父亲的情况 //low[cur] = min(low[i],num[cur]); //wrong //low[cur] = min(low[i],low[cur]); //wrong low[cur] = min(num[i],low[cur]); //right 给父亲的自己能连接到祖先 (那一个) //low[cur] = num[i]; //wrong 反例 //父的父,我的父亲 }//没经过我爹的,就是最后index而不会超过我,只能是在if里面//只有经过我爹的才能 }return;}int main(){int i,j;int t1,t2;scanf("%d %d",&n,&m);for(i = 1;i <= n;i ++)for(j = 1;j <= n;j ++)e[i][j] = 0;for(i = 1;i <= m;i ++){scanf("%d %d",&t1,&t2);e[t1][t2] = 1;e[t2][t1] = 1;}for(i = 1;i <= n;i ++)flag[i] = 0;for(i = 1;i <= n;i ++)num[i] = 0;for(i = 1;i <= n;i ++)low[i] = 0;root = 1;dfs(1,root);for(i = 1;i <= n;i ++)if(flag[i] == 1)printf("%d ",i);return 0;
}
low[cur] = min(low[i],low[cur]);if(low[cur] >= num[cur] && cur != root) //wrongif(low[i] >= num[cur] && cur != root) //right
看似等价实则不然
else if(i != father)//low[cur] = min(low[i],num[cur]); //cuo//low[cur] = min(low[i],low[cur]); //cuolow[cur] = min(num[i],low[cur]); //yes//父的父,我的父亲
这也是看似是,而实际上,你若去举个例子很快就能发现问题
事实上
low[cur] = num[i]; //wrong 反例