有向图的强连通分量之Tarjan算法

墨蓝 2022-08-26 12:12 244阅读 0赞

描述：

To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.  
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.  
Now you want to know the minimum steps needed to get the problem proved.

题意：给出n个命题，其中m条以推导出，让你求最少还需要推到多少个让所有命题等价。

分析：我们把每个命题看做是节点，推到看作是有向边，那么题目可以转化为n个顶点m条边的有向图，要求添加最少的边，使得到的图强连通。

定义：

连通分量：相互可达的节点称为连通分量（connecteed component）。

性质：在无向图中，如果从节点 u 可到节点 v ，那么从节点v 必然可到节点 u ，如果节点 u 可到节点 v ，而节点 v 又可达节点 w ，则必然节点 u 可达节点 w ，在加上每个节点

都可达自身，则发现无向图的中存在关系满足 自反性，对称性，传递性。

强连通分量：“相互可达”为有向图的强连通分量（Strongly Connected Componenet，SCC），可看做事一个集合。

如果把一个集合看成点，那么所有的SCC构成一个SCC图，这个SCC图不会存在有向环，因此是一个有向无环图 （DAG）。

求解：如何求解一个有向图的强连通分量呢？Tarjan算法就是很好的解决这个问题。

首先找题目中的强连通分量，把每一个强连通分量缩成一个点，得到一个DAG，那么得到图中所有点入度和出度的最大值就是答案。

首先就是通过一个DFS求出图中的SCC数目，用栈s保存当前scc中的节点，scc\_cnt是scc计数器，而sccno \[ i \] 为 i 所在的scc编号。

vector<int> G[N];
    int pre[N],lowlink[N],sccno[N],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);
    }

代码：

#include <cstdio>
    #include <vector>
    #include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;
    const int N = 25000;
    vector<int> G[N];
    int pre[N],lowlink[N],sccno[N],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 in[N],out[N];
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            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);
            for(int i=1; i<=scc_cnt; i++)  
                in[i]=out[i]=1;
            for(int u=0; u<n; u++)
            {
                for(int i=0; i<G[u].size(); i++)
                {
                    int v=G[u][i];
                    if(sccno[u] != sccno[v])
                        in[sccno[v]]=out[sccno[u]]=0;
                }
            }
            int a=0,b=0;
            for(int i=1; i<=scc_cnt; i++)
            {
                if(in[i])
                    a++;
                if(out[i])
                    b++;
            }
            int ans=max(a,b);
            if(scc_cnt == 1)
                ans=0;
            if(m==0&&n!=1)
                ans=n;
            printf("%d\n",ans);
        }
        return 0;
    }