Network of Schools hoj&poj 强连通分量的应用 经典题！
/*该题第一问是最少在几台电脑上放文件，可以在一瞬间使所有的电脑都接收到文件。考虑在同一个强连通分量重的电脑，如果其中一台接受到文件，那么可以瞬间使这个分量里的所有电脑都接受到文件。所以第一问的答案只需要求缩点以后的入度为0的分量的个数即可。而对于第二问，同样也是对缩点后的新图进行处理。取入度为0的分量数和出度为0的分量数的最大值。即相当于一棵树的叶子和树根。还有一个，当整个图是一个强连通分量，即缩点个数为1时，不需要任何的电脑，此时ans=0.这就是一类题的模型：至少在有向图中添加多少条有向边可以使整个图边一个强连通图，即图中任意两个节点互达。注意used的应用，是对缩点后的图进行处理。Be care！*/#include <stdio.h>#include <cstring>#include <iostream>using namespace std;const int maxn=101;struct edge{ int to,next;}e[maxn*maxn];int head[maxn],dfn[maxn],low[maxn],belong[maxn],stack[maxn],out[maxn],in[maxn];bool vis[maxn];bool used[maxn][maxn];int n,t,cnt,scnt,top;void add(int i,int j){ e[t].to=j; e[t].next=head[i]; head[i]=t++;}void tarjan(int u){ int tt; dfn[u]=low[u]=++cnt; stack[top++]=u; vis[u]=true; for(int i=head[u]; i!=-1; i=e[i].next) { int j=e[i].to; if(!dfn[j]) { tarjan(j); low[u]=min(low[u],low[j]); } else if(vis[j]) low[u]=min(low[u],low[j]); } if(low[u]==dfn[u]) { scnt++; do { tt=stack[--top]; belong[tt]=scnt; vis[tt]=false; } while(u!=tt); }}int main(){ int num; while(scanf("%d",&n)==1) { memset(head,-1,sizeof(head)); memset(e,0,sizeof(e)); memset(used,false,sizeof(used)); cnt=scnt=top=0; t=0; for(int i=1; i<=n; i++) { while(scanf("%d",&num)==1) { if(num==0) break; add(i,num); } } memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(belong,0,sizeof(belong)); memset(vis,false,sizeof(vis)); memset(stack,0,sizeof(stack)); memset(out,0,sizeof(out)); memset(in,0,sizeof(in)); for(int i=1; i<=n; i++) { if(!dfn[i]) tarjan(i); } for(int i=1; i<=n; i++) { for(int j=head[i]; j!=-1; j=e[j].next) { int v=e[j].to; if(belong[i]!=belong[v]&&!used[belong[i]][belong[v]]) out[belong[i]]++,in[belong[v]]++,used[belong[i]][belong[v]]=true; } } int ans=0; for(int i=1; i<=scnt; i++) { if(in[i]==0) ans++; } printf("%d\n",ans); int ans1=0; for(int i=1; i<=scnt; i++) { if(out[i]==0) ans1++; } if(scnt==1) printf("0\n"); else printf("%d\n",max(ans1,ans)); } return 0;}