难度： 绿/蓝

算法： 强连通分量

首先跑强连通分量，缩点（可以不删重边）。以下文字建立在缩完点的图上。

很容易想到，第一小问的答案就是入度为 $0$ 的节点的数量，因为只需要把软件给这些学校即可。

第二小问比较难想。我自己没想到，看了网上的题解才会的。发现这一问是在问加多少条边才能使这个有向无环图变为一个连通图。因为一个连通图里面不存在入度或出度为 $0$ 的点，且不存在入度或出度为 $0$ 的点的图一定是连通图，于是我们可以把出度为 $0$ 的点连向入度为 $0$ 的点，不够配对的连向别的点（或由别的点连向此点，但这都无关紧要）。所以这一问的答案就是出度为 $0$ 的点数和入度为 $0$ 的点数的较大值。

注意特判输入为连通图，即只有一个强连通分量的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,pt[111],ans1,ans2,te;
int l[111],d[111],in[111],s[111],c,t;
vector<int> e[111],k[111];
priority_queue<int> q[111];
stack<int> st;
void tarj(int u){
	l[u]=d[u]=++c;
	st.push(u);
	in[u]=1;
	for(int i=0;i<int(e[u].size());i++){
		int v=e[u][i];
		if(!d[v]){
			tarj(v);
			l[u]=min(l[u],l[v]);
		}
		else if(in[v]) l[u]=min(l[u],d[v]);
	}
	if(l[u]==d[u]){
		t++;
		while(1){
			s[st.top()]=t;
			in[st.top()]=0;
			if(st.top()==u){
				st.pop();
				break;
			}
			st.pop();
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		while(1){
			cin>>a;
			if(a==0) break;
			e[i].push_back(a);
		}
	}
	for(int i=1;i<=n;i++){
		if(!d[i]) tarj(i);
	}
	if(t==1){
		cout<<"1\n0";
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<int(e[i].size());j++){
			if(s[i]!=s[e[i][j]]){
				q[s[i]].push(s[e[i][j]]);
			} 
		}
	} 
	n=t;
	for(int i=1;i<=n;i++){
		while(!q[i].empty()){
			te=q[i].top();
			k[i].push_back(te);
			pt[te]++;
			while(!q[i].empty()){
				if(q[i].top()==te) q[i].pop();
				else break;
			}
		} 
	}
	for(int i=1;i<=n;i++){
		if(pt[i]==0) ans1++;
		if(k[i].empty()) ans2++;
	}
	cout<<ans1<<"\n"<<max(ans1,ans2);
}