menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】OI日记 · 8月2号——Tarjan
2020-08-02 | 【OI】 | 暂无评论 | 33 次阅读 | 335字

    今天上午学习Tarjan求强连通分量。首先引进一个概念:搜索树。
    我们在做DFS搜索时会出现一棵树,如图:

搜索树中,会有许多边。其中,实线是树边,就是搜索树中子节点与父节点相连的边。稀虚线是后向边,又称返祖边,是一个点直

接连向他祖宗的边。红线是后向边,是一个点直接连接他子孙的边。密虚线是横向边,就是不是以上三种的边。
    Tarjan求强连通分量时会有两个数组:low和dfn。low数组是为i或i的子树能够追溯到的最早的栈中节点

的次序号,dfn数组是在DFS中该节点i被搜索的次序(时间戳),也就是被访问的时间。在Tarjan深搜时,如果发现子节点的low值低

于父节点的low值,那么就直接将父节点的low值赋到子节点上,回溯时也是如此。当回溯到一个点他的dfn值与low值相等时,一个

强连通分量就求出来了。下面放个视频来体现以下过程。视频当中中括号里的值就是low值。

最后,上代码:

#include <bits/stdc++.h>
#include <windows.h>
#define MAXN 1005
using namespace std;
vector <int> edge[MAXN];
int dfn[MAXN],low[MAXN];
stack <int> st;
bool in_st[MAXN];
int cnt;
int ans;
bool aa[MAXN];
int m,n;
int scc[MAXN],sc;
int sz[MAXN];
void input()
{
    cin>>n>>m;
    int tmp1,tmp2;
    for (int i=1;i<=m;i++)
    {
        cin>>tmp1>>tmp2;
        edge[tmp1].push_back(tmp2);
    }
}
void tarjan(int x)
{
    st.push(x);
    in_st[x]=1;
    dfn[x]=++cnt;
    low[x]=cnt;
    for (int i=0;i<edge[x].size();i++)
    {
        int y=edge[x][i];
        if (!dfn[y]) 
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if (in_st[x]) low[x]=min(low[x],low[y]);
    }
    if (dfn[x]==low[x])
    {
        ++sc;
        while (st.top()!=x) {
          scc[st.top()]=sc;
          sz[sc]++;
          in_st[st.top()] = 0;
          st.pop();
        }
        scc[st.top()] = sc;
        sz[sc]++;
        in_st[st.top()] = 0;
        st.pop();
    }
}
int main()
{
    input();
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(1);
    for (int i=1;i<=n;i++)
    if (!aa[scc[i]])
    {
        ans++;
        aa[scc[i]]=1;
    }
    cout<<ans<<endl;
    return 0;
}

    在代码实现过程中,还要注意:在每一层搜索完成后,需要再次更新low值,并取出强连通分量。

None
发表评论
暂无评论
textsms
account_circle
email
link