题目大意
有N个学校，这些学校之间用一些单向边连接，若学校A连接到学校B（B不一定连接到A），那么给学校A发一套软件，则学校B也可以获得。现给出学校之间的连接关系，求出至少给几个学校分发软件，才能使得所有的学校均可以获得软件；以及，至少需要添加几条单向边连接学校，才能使得给这些学校中任何一所发软件，其余的学校均可以收到。
题目分析
在一个图中，强连通分支内的任何一个点被“发软件”，则分支内的所有点均可以获得，因此首先求出强连通分支，将强连通分支合并为一点来看。
重构之后的图若只有一个点，则只需要向任何一所学校发送即可。即结果为1（至少向1所学校发布软件） 0（不需要添加新边来使得整个图连通）.
重构之后的图若有多个点，则考虑这些点中入度为0的点：入度为0的点不能被其他点到达，而一个入度不为0的点可以从某个入度为0的点到达，那么只需要向这些入度为0的点分发软件，就可以使得所有的点均能获得软件。
重构之后的图中有出度为0的点，在图中，入度为0的点（设为m个）无法从其他点到达，那么为了使得所有的点连通，需要m条路径连接到这m个入度为0的点；而出度为0的点（设为n个）无法到达其他点，那么为了使得所有的点连通，需要n条路径从这n个出度为0的点连出。于是，至少需要添加 max(m, n)条边，使得图中所有的点的入度和出度不为0.
同时，在一个有向无环图中，如果该图的所有点均可连接到一块，且每个点的出度和入度均不为0，则该图肯定强连通。于是，结果为 max(m,n)
题意转自：https://www.cnblogs.com/gtarcoder/p/4871267.html
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
vector<int> G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn];
int in[maxn], out[maxn];
int dfs_clock, scc_cnt, n;
stack<int> s; void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
s.push(u);
for(int i=; i<G[u].size(); i++)
{
int v = G[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if(!sccno[v])
lowlink[u] = min(lowlink[u], pre[v]);
}
if(lowlink[u] == pre[u])
{
scc_cnt++;
for(;;)
{
int x = s.top(); s.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
} void calcu()
{
int t1 = , t2 = ;
mem(in, );
mem(out, );
dfs_clock = scc_cnt = ;
mem(sccno, );
mem(pre, );
for(int i=; i<=n; i++)
if(!pre[i])
dfs(i);
for(int i=; i<=n; i++)
for(int j=; j<G[i].size(); j++)
if(sccno[i] != sccno[G[i][j]])
out[sccno[i]]++, in[sccno[G[i][j]]]++;
for(int i=; i<=scc_cnt; i++)
{
if(in[i] == )
t1++;
if(out[i] == )
t2++;
}
if (scc_cnt == ) printf("1\n0\n");
else
printf("%d\n%d\n",t1,max(t2,t1)); } int main()
{
cin>> n;
for(int i=; i<=n; i++)
{
for(;;)
{
int v;
cin>> v;
if(v == ) break;
G[i].push_back(v); }
}
calcu(); return ;
}