题目链接：http://poj.org/problem?id=1236
题目大意：N(2<N<100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
也就是： 给定一个有向图，求： 1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点 2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
分析：首先找出强连通分量，然后把每个强连通分量缩成一个点，得到一个DAG。接下来，设有ａ个结点（别忘了，这里的每个结点对应于原图的一个强连通分量）入度为０，ｂ个结点的出度为０，则max(a,b)就是２的答案（注意特殊情况：当原图已是强连通时，答案是０而不是１），ａ为１的答案。
加边的方法： 要为每个入度为0的点添加入边，为每个出度为0的点添加出边 若 m <= n，则加了这n条边后，已经没有入度0点，则问题解决，一共加了n条边 若 m > n，则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加m-n条边。 所以，max(m,n)就是第二个问题的解
Code:(仅供参考)
/*割点和桥*/ #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<math.h> #include<queue> #include<map> #include<set> #include<stack> #include<stdlib.h> using namespace std; typedef long long LL; const int maxn=210;//点的个数 const int maxm=5010;//边的个数 int low[maxn],dfn[maxn],head[maxn],sccno[maxn]; int tot,Index,scc; stack<int>s; struct edge { int to,next; } eg[maxm]; void addedge(int u,int v) { eg[tot].to=v; eg[tot].next=head[u]; head[u]=tot++; } void Tarjan(int u) { low[u]=dfn[u]=++Index; s.push(u); for(int i=head[u]; i!=-1; i=eg[i].next) { int v=eg[i].to; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { scc++;//强连通分量的个数 for(;;) { int x=s.top(); s.pop(); sccno[x]=scc;//每个点属于哪一个强连通分量 if(x==u) break; } } } void init()//初始化 { while(!s.empty()) s.pop(); tot=0,Index=0,scc=0; memset(head,-1,sizeof(head)); memset(sccno,0,sizeof(sccno)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); } int in[maxn],out[maxn]; int main() { int n,x; scanf("%d",&n); init(); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=1; i<=n; i++) { while(~scanf("%d",&x)&&x) addedge(i,x); } for(int i=1; i<=n; i++) { if(!dfn[i]) Tarjan(i); } for(int u=1;u<=n;u++) { for(int i=head[u];i!=-1;i=eg[i].next) { int v=eg[i].to; if(sccno[u]!=sccno[v]) { in[sccno[v]]++;//入度 out[sccno[u]]++;//出度 } } } int ans1=0,ans2=0; for(int i=1;i<=scc;i++) { if(!in[i]) ans1++;//入度为０的点的个数 if(!out[i]) ans2++;//出度为０的点的个数 } int ans=max(ans1,ans2); if(scc==1)//注意 ans=0; printf("%d\n%d\n",ans1,ans); }
