题目： http://poj.org/problem?id=1236
【题意】
N(2<N<100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
【题解】
找强连通分量，缩点。记f[i]为缩完点后的新图中各点入度，g[i]为出度，ans1为f[i]==0的点的数目，ans2为g[i]==0的点的数目则第一问为ans1，第二问则为max{ans1，ans2}。
至于第二问的解释，我的想法是对于得到的DAG图，考虑其中的出度为0的点和入度为0的点组成的点集V，将这些点相连，最多这需要max{ans1，ans2}条边，就能使整个图成为强连通分量。
但是请注意，大家可能都没发现，这个结论的前提是DAG图是连通的情况下才成立。如果DAG图有多个连通分量，则还要考虑将多个连通分量合并的所需代价。幸运的是，这道题保证了只有一个连通分量。（题目第一句话所说）（无回路有向图） 第二问我也不怎么懂，暂且记住吧
#include <iostream>
#include <stack>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#define N 1010
using namespace std;
struct node
{
int x,y,next;
} eg[];
int n,tt,cnt,ti,ins[N],head[N],low[N],dfn[N],be[N],in[N],ch[N],map[N][N];
stack<int>q;
void init()
{
tt=cnt=;//cnt用于计算强联通分量的个数
ti=;
memset(head,-,sizeof(head));
memset(ins,,sizeof(ins));
memset(in,,sizeof(in));
memset(ch,,sizeof(ch));
memset(map,,sizeof(map));
memset(be,,sizeof(be));
while(!q.empty()) q.pop();
}
void add(int xx,int yy)
{
eg[tt].x=xx;
eg[tt].y=yy;
eg[tt].next=head[xx];
head[xx]=tt++;
}
void tarjan(int i)
{
int w;
low[i]=dfn[i]=++ti;
q.push(i);
ins[i]=;
for(int j=head[i]; j!=-; j=eg[j].next)
{
w=eg[j].y;
if(!dfn[w])
{
tarjan(w);
low[i]=min(low[i],low[w]);
}
else if(ins[w])//有向图的横跨边
{
low[i]=min(low[i],dfn[w]);
}
}
if(dfn[i]==low[i])
{
cnt++;
do
{
w=q.top();
q.pop();
ins[w]=;
be[w]=cnt;//属于哪个强连通分量
}
while(!q.empty()&&i!=w);
}
}
void solve()
{
memset(dfn,,sizeof(dfn));
for(int i=; i<=n; i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
if(cnt==)
{
printf("1\n0\n");
return ;
}
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(map[i][j]&&be[i]!=be[j])
{
in[be[j]]++;
ch[be[i]]++;
}
}
}
int sum=;
int count=;
for(int i=; i<=cnt; i++)
{
if(in[i]==) sum++;
if(ch[i]==) count++;
}
printf("%d\n%d\n",sum,max(sum,count));
return ;
}
int main()
{
int xx;
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=; i<=n; i++)
{
while(scanf("%d",&xx)!=EOF&&xx!=)
{
map[i][xx]=;
add(i,xx);
}
}
solve();
}
return ;
}
强连通分量构成连通图