题意是告诉你有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 ;
}
05-11 19:24