Network of Schools
题意：若干个学校组成一个计算机网络系统，一个学校作为出发端连接着若干个学校，信息可以传送到这些学校。被链接的学校不需要再次与出发端相连，现在问你：A:最少选几个学校作为出发端其他所有的学校都能接收到信息，B：如果任意选一个学校作为出发端使得其他所有学校都能接收到信息，最少需要再搭建几条网线。
思路：用Tarjan算法求出所有的连通分量，然后将这些分量作为一个点进行连接（缩点）。答案A既是入度为0的点的数量，答案B：一条网线可以作为一个出度和一个入度，所以答案B既是出度为0的数量与入度为0的数量的最大值。需要注意的是：如果缩点后只有一个连通分量，那么直接输出1\n0\n。
int belong[N],v1[N],v2[N]; void init() { ti=top=c=0; for(int i=0; i<N; i++) { vis[i]=0; low[i]=0; Stack[i]=0; g[i].clear(); } memset(belong,0,sizeof(belong)); memset(v1,0,sizeof(v1)); memset(v2,0,sizeof(v2)); } void tarjin(int u) { int v; low[u]=dfn[u]=++ti; Stack[top++]=u; vis[u]=1; for(int i=0; i<g[u].size(); i++) { v=g[u][i]; if(!dfn[v]) { tarjin(v); low[u]=min(low[u],low[v]); } else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { c++; do { v=Stack[--top]; vis[v]=0; belong[v]=c; } while(v!=u); } } void solve() { for(int i=1; i<=n; i++) if(!dfn[i]) tarjin(i); //缩点 for(int i=1;i<=n;i++) { for(int j=0;j<g[i].size();j++) { int u=g[i][j]; if(belong[i]!=belong[u]) { v1[belong[i]]++;//出度 v2[belong[u]]++;//入度 } } } int ans1=0,ans2=0; for(int i=1;i<=c;i++) { if(!v1[i]) ans1++; if(!v2[i]) ans2++; } printf("%d\n%d\n",ans2,c==1?0:max(ans1,ans2)); } int main() { while(~scanf("%d",&n)) { // init(); int u; for(int i=1; i<=n; i++) { scanf("%d",&u); while(u) { g[i].push_back(u); scanf("%d",&u); } } solve(); } return 0; }
