misschuer

常用链接

统计

积分与排名

百事通

最新评论

强连通分量的核心算法 无聊贴下

/*
1. 数组的初始化:当首次搜索到点p时,Dfn与Low数组的值都为到该点的时间。
2. 堆栈:每搜索到一个点,将它压入栈顶。
3. 当点p有与点p’相连时,如果此时(时间为dfn[p]时)p’不在栈中,p的low值为两点的low值中较小的一个。
4. 当点p有与点p’相连时,如果此时(时间为dfn[p]时)p’在栈中,p的low值为p的low值和p’的dfn值中较小的一个。
5. 每当搜索到一个点经过以上操作后(也就是子树已经全部遍历)的low值等于dfn值,则将它以及在它之上的元素弹出栈。
   这些出栈的元素组成一个强连通分量。
6. 继续搜索(或许会更换搜索的起点,因为整个有向图可能分为两个不连通的部分),直到所有点被遍历。
*/

void tarjan(int u) {
    
    dfn[ u ] 
= low[ u ] = indeu ++;
    S.push(u);
    
    instack[ u ] 
= true;
    
    
for(int i = p[ u ]; i != -1; i = e[ i ].neut) {
        
              
int v = e[ i ].v;
            
if(dfn[ v ] == -1) {
                
                tarjan(v);
                low[ u ] 
= min(low[ u ], low[ v ]);
            }
            
else if(instack[ v ])
                low[ u ] 
= min(low[ u ], dfn[ v ]);
    }
    
    
if(low[ u ] == dfn[ u ]) {
        
        
while(true) {
            
            
int tmp = S.top();
            S.pop();
            
            belong[ tmp ] 
= cnt;
            instack[ tmp ] 
= false;
            
            
if(tmp == u) break;
        }
        cnt 
++;
    }
}

posted on 2011-03-31 12:49 此最相思 阅读(189) 评论(0)  编辑 收藏 引用


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