题目描述
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 \(B\) 在 \(A\) 学校的分发列表中，\(A\) 也不一定在 \(B\) 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
输入格式
输入文件的第一行包括一个正整数 \(N\)，表示网络中的学校数目。学校用前 \(N\) 个正整数标识。
接下来 \(N\) 行中每行都表示一个接收学校列表（分发列表），第 \(i+1\) 行包括学校 \(i\) 的接收学校的标识符。每个列表用 \(0\) 结束，空列表只用一个 \(0\) 表示。
输出格式
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数，表示子任务 A 的解。
第二行应该包括一个非负整数，表示子任务 B 的解。
样例输入
5
2 4 3 0
4 5 0
0
0
1 0
样例输出
1
2
提示
\(2 \le N \le 100\)。
这道题有两个任务，写起来都十分简单，但必须理解其思路
看到题目中有分发软件这一关系，不难发现这是一道图论的题目，而一个学校接到软件后会立即发出去，很明显，只要在这个强连通分量的所有点都会接收到软件，那这道题就变成了一道缩点的题目
缩点后，对于任务1，我们可以统计所有入度为0的点，因为这些点没有任何别的点给他们发软件，这个不难理解
但对于任务2，我们需要同时统计所有入度为0，和所有出度为0的点，然后取较大值
首先我们要知道，一个有向图缩完点肯定是一个DAG（有向无环图），题目要想把它变成任何两点都可到达，也就是变成一个强连通图
也就是说如果要让DAG变成强连通图，就需要让所有的点都有入度和出度
如果我们把一个没有出度和一个没有入度的点相连，这就保证了两个点都有出入度
可是当我们把所有点连完时，也许会多出几个出度（或入度）为0的点，这就是为什么要取较大值
（还有个比较坑的点，如果他给你的图就是一个强连通图，那么你就不需要连边了，这个需要特判）
\(Code:\)
#include<bits/stdc++.h>
using namespace std;
int n,cnt,inx,top,sum,in_ans,out_ans;
const int N=105,M=10005;
struct edge{
int next,to;
}e[M];
int h[N],dfn[N],low[N],stk[N],vis[N],belong[N],in[N],out[N];
void add(int x,int y){
e[++cnt]=(edge){h[x],y};
h[x]=cnt;
}
void Tarjan(int x){
dfn[x]=low[x]=++inx;
stk[++top]=x;vis[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
sum++;int y=0;
do{
y=stk[top--];
vis[y]=0;
belong[y]=sum;
}while(x!=y);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
while(true){
int x;
scanf("%d",&x);
if(!x) break;
add(i,x);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;i++){
int x=belong[i];
for(int j=h[i];j;j=e[j].next){
int y=belong[e[j].to];
if(x!=y) in[y]++,out[x]++;
}
}
for(int i=1;i<=sum;i++){
if(!in[i]) in_ans++;
if(!out[i]) out_ans++;
}
if(sum==1) printf("%d\n%d",1,0);//如果sum为1，很明显原图就是一个强连通图
else printf("%d\n%d",in_ans,max(in_ans,out_ans));
return 0;
}