MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
就是刨了这个点,此图就不连通了。
解释遍地都是,我就不班门弄斧了, 贴个代码,有错请指出,谢谢

#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, 
0sizeof(map));
        memset(judge, 
0sizeof(judge));
        rootcount 
= 0;cutlen = time = 0;
        memset(b, 
0sizeof(0));
        memset(minf, 
0sizeof(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;
}


posted on 2009-10-06 23:44 memorygarden 阅读(317) 评论(2)  编辑 收藏 引用 所属分类: 图论

Feedback

# re: 图的割点 2012-10-30 21:15 zhangk
if(c == true)cut[cutlen++] = u;
似乎是
if(c == false)cut[cutlen++] = u;
  回复  更多评论
  

# re: 图的割点 2012-10-30 21:43 zhangk
不好意思。理解错了。割点可能在环上。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理