Tarjan算法 POJ2186

ゝ一纸荒年。 2022-11-27 11:30 202阅读 0赞

###### 题目链接 [点击这里][Link 1] ######

###### Tarjan算法 ######

##### 适用情形 #####

有向图，求强连通分量。  
此题中，以Tarjan算法为基础，求解并标记了相应的连通分量，并通过各连通分量出度的分析，找到相应的缩点，并根据缩点的个数，做出相应的处理。

##### 原理简述 #####

Tarjan算法基于对图的深度优先搜索算法，每个强连通分量，都是搜索树中的一颗子树，并在回溯时，判断是否为强连通分量。算法的实现过程，类似于基于后续的深度优先搜索与并查集的组合。

##### 步骤 #####

dfn【i】：记录节点i在深度优先搜索中的访问次序  
low【i】：记录节点i可以到达的访问时间最早的祖先  
st ： 记录节点的栈

1、输入一张有向图图，并以vector通用方式储存。

2、初始化各变量，标记相应指定信息。

3、对于每个未曾访问的节点，都以深度优先搜索的方式来进行遍历。

4、在遍历过程中，对每个访问到的新节点初始化其时间戳及最早访问时间。  
一路把标记的节点压入栈，并将这一节点所能到达的其他节点进行遍历（都以深度优先搜索的方式）。

5、对于每一个u，其相邻节点v的处理，我们分两种情形，

5.1、如果相邻的节点，是未曾访问的新节点，以深度优先搜索的方式访问这一节点，并在访问之后，回溯的过程中，以新节点l的ow【v】与当前节点的low【u】的值中较小的一个，来维护当前节点的最小值。

5.2、如果相邻节点，在是已经被访问过的节点，且节点在栈中，未被弹出，则将用这一节点的dfn次序和当前节点low值中较小的一个，来维护当前节点的low值；

6、在遍历完当前节点所有的相邻节点，并在要回溯到上一节点之前。

6.1、如果这时，low【i】==dfn【i】，说明它无法到达它的任意祖先。

6.2、而在栈里面的i和i之后的点一定是能够与i互达的（否则之前就会被弹出栈）;

6.3、所以，i与站里i之后的点，形成了一个极大强连通分量，这一部分可以作为一个整体弹出。

7、在弹出的过程中，我们对其所属的连通分量，进行记录并标号即可。

8、Tarjan算法基本完成，本题中，利用已经标号好的连通分量，我们统计其出度，找到出度为0的缩点。

9、如果缩点数量是1，直接统计并输出输出牛的数量即可（受其他所有牛仰慕的牛，可能不止一个）

否则，牛的数量为0。

##### 代码 #####

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <stack>
    #include <cstring>
    
    
    using namespace std;
    
    const int max_n=10000+10;
    const int max_m=50000+10;
    
    // 图的表示
    int n,m;
    vector<int> g[max_n];
    // 时间戳与连通分量数
    int index,scc;
    // 深搜利用栈
    stack<int> st;
    // 记录节点可以到达的最早祖先
    int low[max_n];
    // 记录节点在深度优先搜索中的访问次序
    int dfn[max_n];
    // 标记每个变量属于第几个连通分量
    int fa[max_n];
    bool in_stack[max_n];
    // 记录每个连通分量的出度
    int cnt[max_n];
    
    
    void init()
    {
        
        scc=0;
        index=0;
        memset(dfn,0,sizeof(dfn));
        memset(in_stack,false,sizeof(in_stack));
        memset(low,0,sizeof(low));
        memset(cnt,0,sizeof(cnt));
    }
    
    
    
    void tarjan(int u)
    {
        
        dfn[u]=low[u]=++index;
        in_stack[u]=true;
        st.push(u);
        int v;
        for(int i =0;i<g[u].size();++i)
        {
        
            v=g[u][i];
            if(!dfn[v])
            {
        
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(in_stack[v])
            {
        
                low[u]=min(low[u],dfn[v]);
            }
        }
    
        if(dfn[u]==low[u])
        {
        
            ++scc;
            do
            {
        
                v=st.top();
                st.pop();
                fa[v]=scc;
                in_stack[v]=false;
            }while(v!=u);
        }
    }
    
    
    
    int main()
    {
        
        // 输入图
        scanf("%d %d",&n,&m);
        int u,v;
        for(int i=0;i<m;++i)
        {
        
            scanf("%d %d",&u,&v);
            g[u].push_back(v);
        }
    
        // 初始化
        init();
    
        // 求连通分量
        for(int i=1;i<=n;++i)
        {
        
            if(!dfn[i])
            {
        
                tarjan(i);
            }
        }
    
        // 统计出度
        for(int i=1;i<=n;++i)
        {
        
            for(int j=0;j<g[i].size();++j)
            {
        
                int v=g[i][j];
                if(fa[i]!=fa[v])
                {
        
                    ++cnt[ fa[i] ];
                }
            }
        }
    
        // 统计出度为0的缩点
        int ans=0;
        for(int i=1;i<=scc;++i)
        {
        
            if(!cnt[i])
            {
        
                u=i;
                ++ans;
            }
        }
    
        if(ans==1)
        {
        
            ans=0;
            for(int i=1;i<=n;++i)
            {
        
                if(fa[i]==u)
                {
        
                    ++ans;
                }
            }
            printf("%d\n",ans);
        }
        else
        {
        
            printf("0\n");
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=2186