首页 > 其他 > 详细

hdu1269 迷宫城堡,有向图的强连通分量 , Tarjan算法

时间:2014-08-03 23:22:56      阅读:446      评论:0      收藏:0      [点我收藏+]

hdu1269 迷宫城堡

验证给出的有向图是不是强连通图。。。



Tarjan算法板子题


Tarjan算法的基础是DFS,对于每个节点、每条边都搜索一次,时间复杂度为O(V+E)。

算法步骤:

1、搜索到某一个点时,将该点的Low值标上时间戳,然后将自己作为所在强连通分量的根节点(就是赋值Dfn=Low=time)
2、将该点压入栈。
3、当点p有与点p’相连时,如果此时p’不在栈中,p的low值为两点的low值中较小的一个。
4、当点p有与点p’相连时,如果此时p’在栈中,p的low值为p的low值和p’的dfn值中较小的一个。
      注释:因为此时在栈中,所以p‘的强连通分量的父节点需要重新指向(感觉学过并查集理解得更快一些) 。

5、当子树全部遍历完毕,将low值等于dfn值,则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。
   这里的子树全部遍历完毕不是指的所有子节点遍历完毕,而是一个强连通分量的搜索树遍历完毕。
6、选择一个未搜索的节点作为根节点进行搜索,直到所有节点搜索完毕为止。


#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;

const int maxn = 100000 + 10;

vector<int> G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u){
    pre[u] = lowlink[u] = ++ dfs_clock;
    S.push(u);
    for(int i=0; i<G[u].size(); ++i){
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u]){
        scc_cnt++;
        for(;;){
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}

void find_scc(int n){
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof sccno);
    memset(pre, 0, sizeof pre );
    for(int i=0; i<n; ++i)
        if(!pre[i]) dfs(i);
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        if(n==0 && m==0) break;
        for(int i=0; i<n; ++i) G[i].clear();
        for(int i=0; i<m; ++i)
        {
            int u, v;
            scanf("%d%d", &u, &v); u--; v--;
            G[u].push_back(v);
        }

        find_scc(n);

        if(scc_cnt == 1) puts("Yes");  //强连通分量只有一个则说明原图就是强连通图。
        else puts("No");
    }
}


hdu1269 迷宫城堡,有向图的强连通分量 , Tarjan算法,布布扣,bubuko.com

hdu1269 迷宫城堡,有向图的强连通分量 , Tarjan算法

原文:http://blog.csdn.net/yew1eb/article/details/38361465

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!