UVAlive4287_Proving Equivalences

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

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

命题为点，关系为有向边，题目转化成为至少增加多少条有向边使得整个图强连通。

首先对于有向图，求出所有的联通分量，并且将所有的联通分量缩成一个点，最终得出一个无环图。

在新图里，设有A个出度为0的点，B个入度为0的点，那么我们只要保证增加max(A,B)条边就可以保证整个图是强连通的。

这个理解不是很难，只要把所有出度为0的点引出一条边，保证每个入度为0的点引入一条边就可以了。

召唤代码君：

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 200200

using namespace std;

int first[maxn],to[maxn],next[maxn],edge;

int d[maxn],low[maxn],belong[maxn],stack[maxn],top;

int ind[maxn],outd[maxn],U[maxn],V[maxn];

int n,m,T,scc,ans1,ans2;

void _init()

{

    ans1=ans2=scc=top=,edge=-;

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

    {

        first[i]=-;

        d[i]=low[i]=belong[i]=;

    }

}

void addedge(int uu,int vv)

{

    edge++;

    to[edge]=vv,next[edge]=first[uu],first[uu]=edge;

}

void dfs(int cur,int fa)

{

    d[cur]=low[cur]=d[fa]+;

    stack[++top]=cur;

    for (int i=first[cur]; i!=-; i=next[i])

    {

        if (belong[to[i]]) continue;

        if (!d[to[i]]) dfs(to[i],cur);

        low[cur]=min(low[cur],low[to[i]]);

    }

    if (low[cur]>=d[cur])

        for (scc++,ind[scc]=outd[scc]=;stack[top+]!=cur;) belong[stack[top--]]=scc;

}

int main()

{

    scanf("%d",&T);

    while (T--)

    {

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

        _init();

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

        {

            scanf("%d%d",&U[i],&V[i]);

            addedge(U[i],V[i]);

        }

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

            if (!d[i]) dfs(i,);

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

        {

            if (belong[U[i]]==belong[V[i]]) continue;

            outd[belong[U[i]]]++;

            ind[belong[V[i]]]++;

        }

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

        {

            if (ind[i]==) ans1++;

            if (outd[i]==) ans2++;

        }

        if (scc==) ans1=ans2=;

        printf("%d\n",max(ans1,ans2));

    }

    return ;

}