题目链接：http://poj.org/problem?id=1236
题意：有n个学校，学校之间的网络由单向边连接，现在有一个软件要传向每个学校，（单向连通的可以直接传达）
问最少要传给多少个学校可以全部传达？
再至少添加几条单向边，可以随便发送给一个学校使全部学校传达到。
思路：
先找到连通分量，每个连通分量入度为0的就是要传达的，第一问就是入度为0的个数
第二问就是添加几条边可以得到使整个图变成一个强连通分量，答案就是连通分量入度为0的个数和出度为0的个数中最大的那个值
原因：我们将缩完点之后的图看成一个个子树，要想把它们变成一个连通分量就要将出度为0和入度为0的点连起来。
所以只要只要找两者最大的就行。
为什么缩点后再计算出度入度呢？
因为不缩点的话，可能有环，以一个一个点为单位用出度是算不出答案来，只有以一个一个连通分量为单位，计算出度入度。
代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int maxn=105;struct node{ ???int to,next;}edge[maxn*maxn];int head[maxn],low[maxn],dfn[maxn],st[maxn];//st模拟栈 int in[maxn],out[maxn],visit[maxn],belong[maxn];//belong每个点属于哪个连通分量 int n,num,cnt,tot,top,ans1,ans2;void init()//初始化 { ???memset(head,-1,sizeof(head)); ???memset(visit,0,sizeof(visit)); ???memset(dfn,0,sizeof(dfn)); ???memset(low,0,sizeof(low)); ???memset(in,0,sizeof(in)); ???memset(out,0,sizeof(out)); ???memset(st,0,sizeof(st)); ???memset(belong,0,sizeof(belong)); ???ans1=ans2=cnt=tot=num=top=0;}void add(int u,int v)//前向星加边 { ???edge[cnt].to=v; ???edge[cnt].next=head[u]; ???head[u]=cnt++;}void tarjan(int u)//tarjan缩点 { ???dfn[u]=low[u]=++tot;//赋初值 ????visit[u]=1;//标记进栈 ????st[++top]=u;//进栈 ????for(int i=head[u];i!=-1;i=edge[i].next)//搜索相连的边 ????{ ???????int v=edge[i].to; ???????if(!dfn[v])//没有被搜索过 ????????{ ???????????tarjan(v);//搜索 ????????????low[u]=min(low[u],low[v]); ???????????} ???????else if(visit[v])//搜索过，已经在栈里 ????????????low[u]=min(low[u],dfn[v]); ???} ???if(dfn[u]==low[u])//一个连通分量 ????{ ???????int t; ???????num++;//联通分量的编号 ????????do{ ???????????t=st[top--];//出栈 ????????????visit[t]=0;//取消标记 ????????????belong[t]=num;//记录所在连通分量 ????????}while(t!=u); ???}}void solve(){ ???for(int i=1;i<=n;i++) ???????if(!dfn[i]) ???????????tarjan(i); ???for(int i=1;i<=n;i++) ???{ ???????for(int j=head[i];j!=-1;j=edge[j].next) ???????{ ???????????int v=edge[j].to; ???????????if(belong[i]!=belong[v])//不是同一个缩点 ????????????{ ???????????????out[belong[i]]++; ???????????????in[belong[v]]++; ???????????} ???????} ???} ???for(int i=1;i<=num;i++) ???{ ???????if(!in[i]) ???????????ans1++; ???????if(!out[i]) ???????????ans2++; ???}}int main(){ ???while(scanf("%d",&n)!=EOF) ???{ ???????init(); ???????int x; ???????for(int i=1;i<=n;i++) ???????{ ???????????while(scanf("%d",&x) && x!=0) ???????????????add(i,x); ???????????????} ???????solve(); ???????ans2=max(ans1,ans2); ???????if(num==1) ???????????printf("1\n0\n"); ???????else ???????????printf("%d\n%d\n",ans1,ans2); ???} ???return 0;}poj1236 Network of Schools(taejan缩点)
原文地址：https://www.cnblogs.com/xiongtao/p/9998195.html