一开始完全没有搞懂题目的意思就下手，但是居然还AC了两个点？
仔细审视了一下题目的意思，发现题目并不难。
对于第一问，我们只需要求缩点后，入度为 0 的点的数量就可以了。
对于第二问，我们的目标是要求缩点后的所有点互相联通（因为只有这样，任选一个点才能互相到达）
我们转换一下含义：缩点后的所有点只有入度和出度都大于0 才为互相联通
所以第二问我们只需要对入度为0的点和出度0的点做个比较，谁大取谁的值输出。
坑点：需要特判一下只有一个联通块的时候，否则会出错。
#include <cstdio>#include <algorithm>#include <cstring>#include <stack>using std::stack;const int N = 233;struct node{ ???int u,v,next; ???node(){} ???node(int _u,int _v,int _next){ ???????u = _u; ???????v = _v; ???????next = _next; ???}}Edge[N*N];int head[N*N],Count;int dfn[N],low[N];//scc_cnt是联通块的个数（缩点后的点的数量//sccno是缩点后的序号 int scc_cnt,step,sccno[N];int n;void AddEdge(int u,int v){ ???Count++; ???Edge[Count] = node(u,v,head[u]); ???head[u] = Count;}void init(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++){ ???????int x; ???????while(scanf("%d",&x) && x!=0){ ???????????AddEdge(i,x); ???????} ???}}stack<int>S;void dfs(int x){ ???dfn[x] = low[x] = ++step; ???S.push(x); ???for(int i = head[x];i;i=Edge[i].next){ ???????int v = Edge[i].v; ???????if(!dfn[v]){ ???????????dfs(v); ???????????low[x] = std::min(low[x],low[v]); ???????} ???????else if(!sccno[v]) low[x] =std::min(low[x],dfn[v]); ???} ???if(low[x] == dfn[x]){ ???????scc_cnt++; ???????while(1){ ???????????int u = S.top(); ???????????S.pop(); ???????????sccno[u] = scc_cnt; ???????????if(x==u) break; ???????} ???}}int To[N],Out[N];int main(){ ???init(); ???for(int i=1;i<=n;i++){ ???????if(!dfn[i]) dfs(i); ???} ???for(int i=1;i<=Count;i++){ ???????if(sccno[Edge[i].u]!=sccno[Edge[i].v]){ ???????????Out[sccno[Edge[i].u]]++; ???????????To[sccno[Edge[i].v]]++; ???????} ???} ???//To入度 Out出度 ????int ask1=0,ask2=0; ???for(int i=1;i<=scc_cnt;i++){ ???????if( !To[i] ) ask1++; ???????if( !Out[i] ) ask2++; ???} ???int End = std::max(ask1,ask2); ???if(scc_cnt==1){ ???????printf("1\n0\n"); ???} ???else{ ???????printf("%d\n%d\n",ask1,End); ???} ???return 0; ???}[tarjan缩点] 洛谷P2746 [USACO5.3]校园网Network of Schools
原文地址：http://www.cnblogs.com/OIerLYF/p/7792595.html