就是刨了这个点,此图就不连通了。
解释遍地都是,我就不班门弄斧了, 贴个代码,有错请指出,谢谢
#include <stdio.h>
#include <string.h>
int map[100][100], m, n, judge[100], rootcount, b[100], minf[100], cut[100], cutlen, time;
int min(int a, int b){
return a > b ? b : a;
}
void dfs(int u){
int v;bool c = false;
judge[u] = true;
b[u] = minf[u] = ++time;
for(v = 1; v <= n; v++){
if(map[u][v]){
if(!judge[v]){//树边
dfs(v);
if(u == 1){if(++rootcount >= 2)c = true;}//若跟节点在搜索树中有2个以上的儿子,则为割点
else{
minf[u] = min(minf[u], minf[v]);//通过回溯更新以当前节点为根的数所能达到的序号最先的祖先节点。
if(minf[v] >= b[u])c = true;//比较子孙节点和当前节点的先序遍历序号,若达到当前节点的祖先,则此点不是割点。
}
}
else minf[u] = min(minf[u], b[v]);//后向边来比较祖先节点的先序遍历序号和当前节点的已知的能达到的序号最先的祖先,取更小进行更新。
}
}
if(c == true)cut[cutlen++] = u;
}
int main(){
freopen("cutpoint.in", "r", stdin);
freopen("cutpoint.out", "w", stdout);
int i, j, u, v;
while(scanf("%d%d", &n, &m) != -1){
memset(map, 0, sizeof(map));
memset(judge, 0, sizeof(judge));
rootcount = 0;cutlen = time = 0;
memset(b, 0, sizeof(0));
memset(minf, 0, sizeof(0));
for(i = 0; i < m; i++){
scanf("%d%d", &u, &v);
map[u][v] = map[v][u] = 1;
}
dfs(1);
puts("cut point : ");
for(i = 0; i < cutlen; i++){
printf("%d ", cut[i]);
}puts("");
}
return 0;
}