题意：有 n 个学校每个学校可以将自己的软件共享给其他一些学校，首先，询问至少将软件派发给多少学校能够使软件传播到所有学校，其次，询问添加多少学校共享关系可以使所有学校的软件能够相互传达。
首先，第一个问题首先就做强连通缩点，对于缩点后的图询问有多少点的入度为 0，因为入度为 0 的分量必然不能通过其他点传达到。第二个问题则是询问入度为 0 和出度为 0 的点个数的最大值。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn=100; 8 const int maxm=1e4+5; 9 10 int head[2][maxn],point[2][maxm],nxt[2][maxm],size[2];11 int n,t,scccnt;12 int stx[maxn],low[maxn],scc[maxn];13 int id[maxn],od[maxn];14 stack S;15 16 int max(int a,int b){ return a>b?a:b;}17 18 void init(){19 memset(head,-1,sizeof(head));20 size[0]=size[1]=0;21 memset(id,0,sizeof(id));22 memset(od,0,sizeof(od));23 }24 25 void add(int a,int b,int c=0){26 point[c][size[c]]=b;27 nxt[c][size[c]]=head[c][a];28 head[c][a]=size[c]++;29 }30 31 void dfs(int s){32 stx[s]=low[s]=++t;33 S.push(s);34 for(int i=head[0][s];~i;i=nxt[0][i]){35 int j=point[0][i];36 if(!stx[j]){37 dfs(j);38 low[s]=min(low[s],low[j]);39 }40 else if(!scc[j]){41 low[s]=min(low[s],stx[j]);42 }43 }44 if(low[s]==stx[s]){45 scccnt++;46 while(1){47 int u=S.top();S.pop();48 scc[u]=scccnt;49 if(s==u)break;50 }51 }52 }53 54 void setscc(){55 memset(stx,0,sizeof(stx));56 memset(scc,0,sizeof(scc));57 t=scccnt=0;58 for(int i=1;i<=n;++i)if(!stx[i])dfs(i);59 for(int i=1;i<=n;++i){60 for(int j=head[0][i];~j;j=nxt[0][j]){61 int k=point[0][j];62 if(scc[i]!=scc[k]){63 add(scc[i],scc[k],1);64 od[scc[i]]++;65 id[scc[k]]++;66 }67 }68 }69 }70 71 int main(){72 scanf("%d",&n);73 init();74 for(int i=1;i<=n;++i){75 int b;76 while(scanf("%d",&b)&&b){77 add(i,b);78 }79 }80 setscc();81 int in=0,out=0;82 for(int i=1;i<=scccnt;++i){83 if(!id[i])in++;84 if(!od[i])out++;85 }86 printf("%d\n%d\n",in,scccnt==1?0:max(in,out));87 return 0;88 }