有向图的强联通分量相关例题（Korasaju算法和Tarjan算法）

迷南。 2024-04-17 05:37 63阅读 0赞

# 有向图的强联通分量相关例题（Korasaju算法和Tarjan算法） #

一、[poj 2186：Popular Cows][poj 2186_Popular Cows]

即：强连通分量+缩点

还是很菜，都是照着大佬的板子敲的，而且还不是很熟练

**Korasaju算法** 实现

/**korasaju算法*/
    
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    const int maxn=10010;
    vector<int>edge1[maxn];     //原图的邻接表
    vector<int>edge2[maxn];     //逆图的邻接表
    
    int End[maxn];        //对原图搜索，顶点的序号
    
    int vis[maxn];
    
    int out[maxn];        //转化为DAG以后的每个缩点的出度
    
    int belong[maxn];     //每个顶点属于哪个集合，相当于染色，当前结点被染成了什么颜色
    
    int setNum[maxn];        //每个颜色包括多少顶点，也就是强联通分量的个数
    
    int color;        //代表不同的颜色
    
    int cnt;            //正向排序的编号
    
    int n,m;          //题目所给的顶点数和边数
    
    /**对原图深度搜索*/
    void dfs1(int i)
    {
        
        vis[i]=1;
        for(int j=0;j<edge1[i].size();j++)
        {
        
            if(vis[edge1[i][j]]==0)
                dfs1(edge1[i][j]);
        }
        End[cnt++]=i;
    }
    /**对逆图进行深度搜索*/
    void dfs2(int i)
    {
        
        vis[i]=1;
        belong[i]=color;
        for(int j=0;j<edge2[i].size();j++)
        {
        
            if(vis[edge2[i][j]]==0)
            {
        
                setNum[color]++;
                dfs2(edge2[i][j]);
            }
        }
    }
    void kosaraju()
    {
        
        color=1;
        cnt=1;
        for(int i=1;i<=n;i++)
            setNum[i]=1;
        memset(out,0,sizeof(out));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
        
            if(vis[i]==0)
                dfs1(i);
        }
        memset(vis,0,sizeof(vis));
        for(int i=cnt-1;i>=1;i--)
        {
        
            if(vis[End[i]]==0)
            {
        
                dfs2(End[i]);
                color++;
            }
        }
    
        /**构造DAG*/
        for(int i=1;i<=n;i++)
        {
        
            for(int j=0;j<edge1[i].size();j++)
            {
        
                if(belong[i]==belong[edge1[i][j]])
                    continue;
                out[belong[i]]++;
            }
        }
    
        //查找每个颜色出度为0的点或缩点，out[i]代表第i中颜色的点或缩点的出度，
        //出度为0唯一,输出该颜色集合中点的个数setNum[i],否则输出0
    
        int res=0;
        int cntt=0;
        for(int i=1;i<color;i++)
        {
        
            if(!out[i])
            {
        
                cntt++;
                res=setNum[i];
            }
            if(cntt==2)
            {
        
                res=0;
                break;
            }
        }
        printf("%d\n",res);
    }
    int main()
    {
        
        while(~scanf("%d%d",&n,&m))
        {
        
            int a,b;
            for(int i=1;i<=m;i++)
            {
        
                scanf("%d%d",&a,&b);
                edge1[a].push_back(b);
                edge2[b].push_back(a);
            }
            kosaraju();
        }
    }

至于想看Tarjan算法具体实现原理，请看这个博客

[https://www.cnblogs.com/five20/p/7594239.html][https_www.cnblogs.com_five20_p_7594239.html]

**Tarjan算法实现**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int maxn=10010;
    const int maxm=50010;
    int n,m;
    int dfn[maxn];
    int low[maxn];
    int head[maxn];
    int vis[maxn];
    int id,id2;
    int scc_num,sec;
    int sta[maxn];        //用数组模拟栈
    int cnt[maxn];
    int out[maxn];
    struct node
    {
        
        int next,to;
    }E[maxm];
    
    void add(int a,int b)
    {
        
        E[id].to=b;
        E[id].next=head[a];
        head[a]=id++;
    }
    void dfs(int i)
    {
        
        dfn[i]=low[i]=++sec;
        vis[i]=1;
        sta[id2++]=i;
        int u,v;
        for(int j=head[i];j!=-1;j=E[j].next)
        {
        
            v=E[j].to;
            if(vis[v]==0)
                dfs(v);
            if(vis[v]==1)
            {
        
                low[i]=min(low[i],low[v]);
            }
        }
        if(dfn[i]==low[i])
        {
        
            ++scc_num;
            do
            {
        
                ++cnt[scc_num];
                u=sta[--id2];
                low[u]=scc_num;
                vis[u]=2;
            }while(u!=i);
        }
    }
    void Tarjan()
    {
        
        int ok=0,ans;
        sec=id2=scc_num=0;
        for(int i=1;i<=n;i++)
        {
        
            if(vis[i]==0)
                dfs(i);
        }
        for(int i=1;i<=n;i++)
        {
        
            for(int j=head[i];j!=-1;j=E[j].next)
            {
        
                if(low[i]!=low[E[j].to])
                {
        
                    out[low[i]]=1;
                    break;
                }
            }
        }
        for(int i=1;i<=scc_num;i++)
        {
        
            if(out[i]==0)
            {
        
                if(++ok>1)
                    break;
                ans=cnt[i];
            }
        }
        if(ok!=1)
            printf("0\n");
        else
            printf("%d\n",ans);
    }
    int main()
    {
        
        int a,b;
        while(~scanf("%d%d",&n,&m))
        {
        
            memset(head,-1,sizeof(head));
            memset(vis,0,sizeof(vis));
            memset(out,0,sizeof(out));
            memset(cnt,0,sizeof(cnt));
            id=0;
            for(int i=1;i<=m;i++)
            {
        
                scanf("%d%d",&a,&b);
                add(a,b);
            }
            Tarjan();
        }
    }

虽然Korasaju算法很容易理解，但是感觉时间复杂度还是比arjan差

而且个人感觉Tarjan算法似乎好用点

二、[hdu 1269：迷宫城堡][hdu 1269]

感觉就是一道裸题，以后再补吧

[poj 2186_Popular Cows]: http://poj.org/problem?id=2186
[https_www.cnblogs.com_five20_p_7594239.html]: https://www.cnblogs.com/five20/p/7594239.html
[hdu 1269]: http://acm.hdu.edu.cn/showproblem.php?pid=1269