Network of Schools（poj1236 Tarjan）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn=110;
 8 int n;
 9 int cnt,head[maxn];
10 int dfn[maxn],low[maxn],scc[maxn],stk[maxn],index=0,sccnum=0,top=0;
11 struct Edge{
12     int v,nxt;
13 }G[maxn*maxn];
14 void init(){ cnt=0; memset(head,-1,sizeof(head)); }
15 void add(int u,int v){
16     G[cnt].v=v;
17     G[cnt].nxt=head[u];
18     head[u]=cnt++;
19 }
20 
21 void tarjan(int root){   //tarjan 模板
22     if(dfn[root]) return;
23     dfn[root]=low[root]=++index;
24     stk[++top]=root;
25 
26     for(int i=head[root];~i;i=G[i].nxt){
27         int v=G[i].v;
28         if(!dfn[v]){
29             tarjan(v);
30             low[root]=min(low[root],low[v]);
31         }
32         else if(!scc[v]){   //如果还在站内
33             low[root]=min(low[root],dfn[v]);
34         }
35     }
36     if(low[root]==dfn[root]){
37         sccnum++;
38         for(;;){
39             int x=stk[top--];
40             scc[x]=sccnum;
41             if(x==root) break;
42         }
43     }
44 }
45 
46 int in[maxn],out[maxn];
47 void solve(){
48     index=0,sccnum=0,top=0;
49     memset(dfn,0,sizeof(dfn));
50     memset(low,0,sizeof(low));
51     memset(scc,0,sizeof(scc));
52     memset(stk,0,sizeof(stk));
53     for(int i=1;i<=n;i++){
54         if(!dfn[i]){
55             tarjan(i);
56         }
57     }
58     if(sccnum==1){   //特判
59         printf("1\n0\n");
60         return;
61     }
62     for(int i=1;i<=sccnum;i++){
63         in[i]=0,out[i]=0;
64     }
65     for(int i=1;i<=n;i++){   //重新建图
66         for(int j=head[i];~j;j=G[j].nxt){
67             int v=G[j].v;
68             if(scc[i]!=scc[v]){
69                 in[scc[v]]++;
70                 out[scc[i]]++;
71             }
72         }
73     }
74     int res1=0,res2=0;
75     for(int i=1;i<=sccnum;i++){
76         if(in[i]==0) res1++;
77         if(out[i]==0) res2++;
78     }
79     printf("%d\n%d\n",res1,max(res1,res2));
80 }
81 
82 int main(){
83     while(scanf("%d",&n)==1){
84         init();
85         for(int i=1,d1;i<=n;i++){
86             while(scanf("%d",&d1)==1&&d1){
87                 add(i,d1);
88             }
89         }
90         solve();
91     }
92     return 0;
93 
94 }