题目：Network of Schools 总结：题目第一问求是缩点之后，入度为0的点的个数。第二问求的是缩点之后，max(入度为0的点的个数,出度为0的点的个数)。可以先用tarjan进行染色。然后再新建立一个图，分别求出它们的入度和出度。
#include <stdio.h> #include <stack> #include <map> #include <vector> #include <string.h> #include <algorithm> using namespace std; typedef pair<int,int>P; const int N = 105; map<P,int>b; stack<int>que; int dfn[N],low[N],num,vis[N]; int colour[N],cnt = 0,in[N],out[N]; vector<int>G[N]; int n; void init(){ memset(out,0,sizeof out); memset(in,0,sizeof in); memset(colour,0,sizeof colour); memset(vis,0,sizeof vis); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); num = 0; cnt = 0; b.clear(); while(!que.empty()){ que.pop(); } } void tarjan(int u){ dfn[u] = low[u] = ++num; que.push(u);//进栈 vis[u] = 1;//表示在栈里面 for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); }else if(vis[v]){//需要在栈里面,才执行 low[u] = min(low[u],dfn[v]); } } if(dfn[u] == low[u]){ int p; ++cnt;//新图的个数 do{ p = que.top(); que.pop(); colour[p] = cnt;//进行染色 vis[p] = 0;//表示出栈 }while(p != u); } } void solve(){ int x; init(); for(int i = 1;i <= n;i++){ while(scanf("%d",&x)&&x){ G[i].push_back(x); } } for(int i = 1;i <= n;i++){ if(!dfn[i]){ tarjan(i); } } if(cnt == 1){ printf("1\n0\n"); return; } for(int i = 1;i <= n;i++){ for(int j = 0;j < G[i].size();j++){ int u = colour[i],v = colour[G[i][j]]; if(u != v && !b[P(u,v)]){ b[P(u,v)] = 1; // printf("%d %d\n",u,v); in[v]++; out[u]++; } } } int ans = 0,ans1 = 0; for(int i = 1;i <= cnt;i++){ if(in[i] == 0) ans++; if(out[i] == 0) ans1++; } printf("%d\n%d\n",ans,max(ans,ans1)); } int main(){ scanf("%d",&n); solve(); return 0; }