POJ1236 Network of Schools

5
2 4 3 0
4 5 0
0
0
1 0

1
2

#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
const int maxn = 100+10;
int n,m,num,cnt,id,head[maxn],ins[maxn],low[maxn],dfn[maxn],belong[maxn],in[maxn],out[maxn];
stack<int> s;
struct Edge{
  int to,next;
}e[maxn*maxn];
void add(int u,int v){
  e[++num].next = head[u];
  e[num].to = v;
  head[u] = num;
}
void Tarjan(int u){
  low[u] = dfn[u] = ++cnt;
  s.push(u);
  ins[u] = 1;
  for(int i = head[u]; i; i = e[i].next){
    int v = e[i].to;
    if(!dfn[v]){
      Tarjan(v);
      low[u] = min(low[u],low[v]);
    }else if(ins[v]){
      low[u] = min(low[u],low[v]);
    }
  }
  if(low[u]==dfn[u]){
    int v;
    id++;
    do{    
      v = s.top();
      s.pop();
      ins[v] = 0; 
      belong[v]=id;//为连通分量标号 
    }while(u!=v);
  }
}
void solveDegree(){//求每个连通分量的入度,出度 
  for(int u = 1; u <= n; u++){//遍历每条边. 求度 
    for(int i = head[u]; i; i = e[i].next){
      int v = e[i].to;
      if(belong[u]!=belong[v]){//中间可能还有平行边呢.. 不过不用想那么多. 
        out[belong[u]]++;
        in[belong[v]]++;
      }
    } 
  }
} 
int main() {
  int v;
  cin>>n;//5
  for(int u = 1; u <= n; u++){
    while(cin>>v&&v){
      add(u,v);
    }
  }
  for(int i = 1; i<=n; i++){
    if(!dfn[i]){
      Tarjan(i);
    }
  }
  if(id==1){//强连通分量为1的特殊处理.
    cout<<1<<endl;
    cout<<0<<endl;
    return 0;
  }
  solveDegree();
  int ans1=0,ans2=0;//统计入度为0的节点个数ans1    出度为0的节点个数ans2. 
  for(int i = 1; i <= id; i++){//统计缩点中入度和出度为1的数量.  这里最多有id个哦.
    if(!in[i]){
      ans1++;
    }
    if(!out[i]){
      ans2++;
    }
  }
  cout<<ans1<<endl;
  cout<<max(ans1,ans2)<<endl;
  return 0;
}