POJ 1236 Network of Schools IOI 1996

1236 -- Network of Schools
Given a network, answer at least how many nodes we need to spread information to let the whole graph know, and the minimum directed edges required to add so the whole graph becomes an SCC.
The first query is just to find the number of nodes that have no in degree.
The second is to find max( count of 0 in degree, count of 0 out degree ), it is't hard to figure it out.
It was a relatively easy problem. However, I forgot to judge for the special case where this general algorithm will fail -- when the count of SCC of the original network is 1, the answer is ( 1, 0 ). I think I should make myself clearer when it comes to corner cases, especially when something is 0 or 1 when solving graph related problems.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 100 + 2;

int n;
vector<int> G[MAXN], G2[MAXN];
vector<int> stk;

int vis[MAXN];
void dfs1(int u){
    vis[ u ] = 1;
    for(int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if( !vis[ v ] ) dfs1( v );
    }
    stk.push_back( u );
}
int scc_cnt, sccno[MAXN];
void dfs2(int u){
    sccno[ u ] = scc_cnt;
    for(int i = 0; i < G2[u].size(); ++i){
        int v = G2[u][i];
        if( !sccno[ v ] ) dfs2( v );
    }
}
void kosaraju(){
    for(int u = 1; u <= n; ++u) if( !vis[ u ] )
        dfs1( u );
    for(int i = stk.size() - 1; i >= 0; --i) if( !sccno[ stk[i] ] )
        ++scc_cnt, dfs2( stk[i] );
}

int in[MAXN], out[MAXN];
void solve(){
    kosaraju();
    if( scc_cnt == 1 ){ // BE CAREFUL NEXT TIME
        puts("1\n0");
        return;
    }
    for(int u = 1; u <= n; ++u)
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i];
            if( sccno[ u ] != sccno[ v ] )
                ++out[ sccno[ u ] ], ++in[ sccno[ v ] ];
        }
    int in_0_cnt = 0, out_0_cnt = 0;
    for(int i = 1; i <= scc_cnt; ++i){
        if( in[ i ] == 0 ) ++in_0_cnt;
        if( out[ i ] == 0 ) ++out_0_cnt;
    }
    printf("%d\n", in_0_cnt);
    printf("%d\n", max( in_0_cnt, out_0_cnt ));
}

int main(){
    scanf("%d", &n);
    for(int u = 1; u <= n; ++u){
        int v;
        while( scanf("%d", &v) == 1 && v ){
            G[ u ].push_back( v );
            G2[ v ].push_back( u );
        }
    }
    solve();
    return 0;
}