2019.08.16 日常总结( 二 ) _学校

<=n;i++)if (!dfn[i]) tarjan(i);for(i=n;i;i--)for(j=h[i];j;j=e[j].next){register int v=e[j].to;if (belong[i]!=belong[v]){++out[belong[i]];++ind[belong[v]];}}if (col==1) printf("1\n0");else{for(i=1;i<=col;i++){if (out[i]==0) out_number++;if (ind[i]==0) ind_number++;}ans=max(ind_number,out_number);printf("%d\n%d",ind_number,ans);}return 0;}
洛谷P2860

文章插图
题意：
为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．
每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．
思路：还是缩点，然后统计叶节点的个数ans ，输出
即可

#include using namespace std;const int N=10100;struct node{int from,next,to;}e[N];int h[N],tot;void add_edge_in_e(int a,int b){e[++tot]=(node){a,h[a],b};h[a]=tot;}int dfscnt,belong[N];int dfn[N],low[N];bool bridge[N];void tarjan(int u,int edge){dfn[u]=low[u]=++dfscnt;//	Stack[++stack_top]=u;for(int i=h[u];i;i=e[i].next){register int v=e[i].to;if (!dfn[v]){tarjan(v,i);low[u]=min(low[u],low[v]);if (dfn[u]>1);return 0;}