出自 IOI 1996
一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校 a 支援学校 b，并不表示学校 b 一定支援学校 a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。
任务a：
请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校；
任务b：
如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。
第一行是一个正整数n(2<=n<=100)，表示与网络连接的学校总数。 随后n行分别表示每个学校要支援的学校，即：i+1行表示第i号学校要支援的所有学校代号，最后以0结束。
如果一个学校不支援任何其他学校，相应行则会有一个0。一行中若有多个数字，数字之间以一个空格分隔。
包含两行，第一行是一个正整数，表示任务a的解；第二行也是一个正整数，表示任务b的解。
5 2 4 3 0 4 5 0 0 0 1 0
1 2
强连通分量+缩点，a任务就是要找出缩点后的新图中出度为0的点的数量，任务b为入度点的数量，模板题，这里要注意特判全部连通的情况！
#include<bits/stdc++.h> using namespace std; const int maxn = 205; int dfn[maxn],low[maxn]; int Stack[maxn],t[maxn],tt[maxn],in[maxn],out[maxn]; bool instack[maxn]; int n,tot,num,cnt; vector<int>e[maxn]; void add_edge(int u , int v) { e[u].push_back(v); } void Tar(int u) { dfn[u] = low[u] = ++tot; Stack[++num] = u; instack[u] = true; for(int i = 0 ; i < e[u].size() ; i++) { int v = e[u][i]; if(!dfn[v]) { Tar(v); low[u] = min(low[u],low[v]); } else if(instack[v]) { low[u] = min(low[u],dfn[v]); } } if(dfn[u] == low[u]) { while(u != Stack[num]) { tt[cnt]++; t[Stack[num]] = cnt; instack[Stack[num]] = false; num--; } t[Stack[num]] = cnt; tt[cnt]++; instack[Stack[num]] = false; num--; cnt++; } } int main() { cin >> n; for(int i = 1 ; i <= n ; i++) { int v; while(cin >> v) { if(v) add_edge(i,v); else break; } } for(int i = 1 ; i <= n ; i++) { if(!dfn[i]) Tar(i); } for(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j < e[i].size() ; j++) { int u = i , v = e[u][j]; if(t[u] != t[v]) { out[t[u]]++; in[t[v]]++; } } } int suma = 0 , sumb = 0; if(cnt == 1) { cout << "1\n0" << endl; return 0; } for(int i = 0 ; i < cnt ; i++) { if(!out[i]) suma++; if(!in[i]) sumb++; } cout << sumb << "\n" << max(sumb,suma) << endl; return 0; }