首页 > 代码库 > UVAlive4287_Proving Equivalences
UVAlive4287_Proving Equivalences
题意是告诉你有n个命题，m条递推关系，表示某个命题可以推出另外一个命题。
现在问你至少在增加多少个递推关系可以保证所有命题两两互推。
命题为点，关系为有向边，题目转化成为至少增加多少条有向边使得整个图强连通。
首先对于有向图，求出所有的联通分量，并且将所有的联通分量缩成一个点，最终得出一个无环图。
在新图里，设有A个出度为0的点，B个入度为0的点，那么我们只要保证增加max(A,B)条边就可以保证整个图是强连通的。
这个理解不是很难，只要把所有出度为0的点引出一条边，保证每个入度为0的点引入一条边就可以了。
召唤代码君：
#include <iostream>#include <cstring>#include <cstdio>#define maxn 200200using 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=0,edge=-1; for (int i=1; i<=n; i++) { first[i]=-1; d[i]=low[i]=belong[i]=0; }}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]+1; stack[++top]=cur; for (int i=first[cur]; i!=-1; 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]=0;stack[top+1]!=cur;) belong[stack[top--]]=scc;}int main(){ scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); _init(); for (int i=1; i<=m; i++) { scanf("%d%d",&U[i],&V[i]); addedge(U[i],V[i]); } for (int i=1; i<=n; i++) if (!d[i]) dfs(i,0); for (int i=1; i<=m; i++) { if (belong[U[i]]==belong[V[i]]) continue; outd[belong[U[i]]]++; ind[belong[V[i]]]++; } for (int i=1; i<=scc; i++) { if (ind[i]==0) ans1++; if (outd[i]==0) ans2++; } if (scc==1) ans1=ans2=0; printf("%d\n",max(ans1,ans2)); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。