LA 4287 等价性证明

题目链接：http://vjudge.net/contest/141990#overview

题意是告诉你有n个命题，m条递推关系，表示某个命题可以推出另外一个命题。

现在问你至少在增加多少个递推关系可以保证所有命题两两互推。

把命题看成一个结点，推导看成有向边，就是n个结点，m 条有向边，要求添加尽量少的边，使得新图强连通。

首先找出强连通分量，把每个强连通分量缩成一个点，得到DAG。设有 a 个结点入度为 0 ，b 个结点出度为 0 ，max(a,b)，就是答案。如下图：

入度为 0 的集合 为 1，出度为 0 的集合 为 2，要加两条红边才能 互相到达（强连通）。

先标记所有强连通图的入度出度 1 ，要是有点相同，标记为 0 ，统计 入度为 1 ，出度为 1 的个数。

如果原图只有一个强连通分量 ans = 0 不需要加边。

#include <bits/stdc++.h>

using namespace std;

const int Maxn =  + ;

vector<int> G[Maxn];

int pre[Maxn];

int lowlink[Maxn];

int sccno[Maxn];

int dfs_clock;

int scc_cnt;

stack<int> S;

void dfs(int u)

{

    pre[u] = lowlink[u] = ++dfs_clock;

    S.push(u);

    for(int i=; 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 = ;

    memset(sccno,,sizeof(sccno));

    memset(pre,,sizeof(pre));

    for(int i=; i<n; i++)

    {

        if(!pre[i])

            dfs(i);

    }

}

int main()

{

    int n,m;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        for(int i=; i<n; i++)

            G[i].clear();

        for(int i=; i<m; i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            u--;

            v--;

            G[u].push_back(v);

        }

        find_scc(n);

        int in0[Maxn];

        int out0[Maxn];

        for(int i=; i<=scc_cnt; i++)

        {

            in0[i] = ;

            out0[i] = ;

        }

        for(int u=; u<n; u++)

        {

            for(int i=; i<G[u].size(); i++)

            {

                int v = G[u][i];

                if(sccno[u]!=sccno[v])

                {

                    in0[sccno[v]] = ;

                    out0[sccno[u]] = ;

                }

            }

        }

        int maxin = ,maxout = ;

        for(int i=; i<=scc_cnt; i++)

        {

            if(in0[i]) maxin ++;

            if(out0[i]) maxout ++;

        }

        int ans = max(maxin,maxout);

        if(scc_cnt==)

            puts("");

        else printf("%d\n",ans);

    }

    return ;

}