其实就是手打了个Tarjan的模板
输出的时候注意是入度为0的点的个数和max（入度0的个数，出度0的个数），在n=1时特判为0即可
——以后图论要渐渐模板化，方便使用
1 #include2 #include 3 using namespace std; 4 struct E 5 { 6 int from,to,next; 7 } e[100001]; 8 int Enum=0,sttop=0; 9 int first[101]; 10 int dfn[101],low[101]; 11 bool que[101]; 12 int tar[101]; 13 int sum,n,_ans,ans; 14 int df; 15 int num[101]; 16 int st[101]; 17 void add(int from,int to) 18 { 19 E New; 20 New.from=from; 21 New.to=to; 22 New.next=first[from]; 23 e[++Enum]=New; 24 first[from]=Enum; 25 } 26 void tarjan_dfs(int u) 27 { 28 st[++sttop]=u; 29 int v; 30 que[u]=1; 31 dfn[u]=low[u]=++df; 32 for(int i=first[u];i;i=e[i].next) 33 { 34 v=e[i].to; 35 if(dfn[v]==0) 36 { 37 tarjan_dfs(v); 38 low[u]=min(low[u],low[v]); 39 } 40 else 41 if(que[v]) 42 low[u]=min(low[u],dfn[v]); 43 } 44 if(dfn[u]==low[u]) 45 { 46 sum++; 47 do 48 { 49 v=st[sttop--]; 50 que[v]=0; 51 tar[v]=sum; 52 }while(u!=v); 53 } 54 } 55 int tarjan() 56 { 57 sum=0;df=0;sttop=0; 58 for(int i=1;i<=n;i++) 59 if(!dfn[i]) 60 tarjan_dfs(i); 61 for(int i=1;i<=n;i++) 62 first[i]=0;//清空原有边 63 for(int i=1;i<=Enum;i++) 64 if(tar[e[i].from]!=tar[e[i].to]) 65 { 66 e[i].from=tar[e[i].from]; 67 e[i].to=tar[e[i].to]; 68 e[i].next=first[e[i].from]; 69 first[e[i].from]=i; 70 num[e[i].to]++; 71 } 72 return sum; 73 } 74 void dfs(int k) 75 { 76 if(first[k]) 77 for(int i=first[k];i;i=e[i].next) 78 dfs(e[i].to); 79 else 80 if(!que[k]) 81 { 82 _ans++; 83 que[k]=1; 84 } 85 } 86 int main() 87 { 88 scanf("%d",&n); 89 for(int i=1;i<=n;i++) 90 { 91 int k; 92 scanf("%d",&k); 93 while(k>0) 94 { 95 add(i,k); 96 scanf("%d",&k); 97 } 98 } 99 n=tarjan();100 for(int i=1;i<=n;i++)101 que[i]=0;102 for(int i=1;i<=n;i++)103 if(!num[i])104 {105 ans++;106 dfs(i);107 }108 printf("%d\n%d\n",ans,n==1?0:max(ans,_ans));109 return 0;110 }