本文共 1359 字，大约阅读时间需要 4 分钟。
时间戳：记录某个顶点在遍历时候是第几个被访问的。
这里用数组num[]记录时间戳.
用数组low[]记录每个顶点在不经过父顶点时，能够会到的最小时间戳.
割点条件：
（1）当前顶点不是根节点，并且满足low[i] >= cur[cur] 则当前顶点为割点。
（2）当前顶点是根节点，并且在生成树中有两个儿子，那么这个根节点是割点。
完整实现：
#include#define MAXVEX 10 #define INF 65535int n, m, e[MAXVEX][MAXVEX];int num[9], low[9];//这里不需要初始化 num[]数组的原因是 它是全局的 默认初始为0int index; //进行时间戳的递增int flag[MAXVEX];int root, child;int min(int a, int b) { return a < b ? a : b; }//割点算法核心void dfs(int cur, int father) { int i; child = 0; index++; num[cur] = index;//当前顶点时间戳 low[cur] = index;//开始时能够访问到的最早的时间戳是自己 for(i = 1; i <= n; i++){ if(e[cur][i] == 1){ if(num[i] == 0){ //没有被访问过 child++;//从生成树的角度来说，此时i为 cur的儿子 dfs(i, cur);//继续往下遍历 low[cur] = min(low[cur], low[i]); if(cur != root && low[i] >= num[cur])//根据条件(1)判断 flag[cur] = 1; if(cur == root && child == 2)//根据条件(2)判断 flag[cur] = 1; } else if(num[i] != 0 && i != father){ low[cur] = min(low[cur], num[i]); } } } } int main() { int i, j, x, y; scanf("%d%d",&m,&n); for(i = 1; i <= n; i++ ){ for(j = 1; j <= n; j++){ if(i == j) e[i][j] = 0; else e[i][j] = INF; } } for(i = 1; i <= m; i++ ){ scanf("%d%d",&x,&y); e[x][y] = 1; e[y][x] = 1; } index = 0; root = 1; dfs(1, 1) ; for(i = 1; i <= n; i++ ){ if(flag[i] == 1) printf("cut_point = %d\n",i); } return 0; }
转载地址：http://mximi.baihongyu.com/