Poj Solution 3180

http://poj.org/problem?id=3180

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

class Graph {
public:
    enum { MAX_NUM_EDGE = 50010, MAX_NUM_NODE = 10010 };
    
    struct Edge {
        int to;
        Edge *next;
    }e[2*MAX_NUM_EDGE];
    int en;

    Edge *e_begin[MAX_NUM_NODE], *e_reverse[MAX_NUM_NODE], *e_end[MAX_NUM_NODE];
    Edge *e_reduced[MAX_NUM_NODE];

    int sign[MAX_NUM_NODE], count;
    int flag[MAX_NUM_NODE];

    int n;
    int st[MAX_NUM_NODE], sn;

    bool reduce;

    void clear( );
    void insertEdge( int form, int to );
    
    int Strongly_Connected_Component( int n, bool reduce = false );

private:
    void Reduced( int m );
    void DFS( int k );
    void RDFS( int k );
};

///////////////////////////////////////////////////////

void Graph::clear( ) {
    n = en = 0;
    memset( e_begin, 0, sizeof e_begin );
    memset( e_reverse, 0, sizeof e_reverse );
    memset( e_end, 0, sizeof e_end );
}

void Graph::insertEdge( int from, int to ) {
    
    e[en].to = to;
    e[en].next = e_begin[from];
    e_begin[from] = &e[en];
    
    if( e_end[from] == 0 )
        e_end[from] = &e[en];
    en++;

    e[en].to = from;
    e[en].next = e_reverse[to];
    e_reverse[to] = &e[en];
    en++;
}

void Graph::DFS( int k ) {
    sign[k] = count;
    for( Edge *p = e_begin[k]; p; p=p->next )
        if( sign[p->to] != count )
            DFS( p->to );
    st[ sn++ ] = k;
}

void Graph::RDFS( int k ) {
    flag[k] = count;
    
    if( reduce && e_begin[k] ) {
        e_end[k]->next = e_reduced[count];
        e_reduced[count] = e_begin[k];
    }

    for( Edge *p = e_reverse[k]; p; p=p->next )
        if( flag[p->to] == -1 )
            RDFS( p->to );
}

int Graph::Strongly_Connected_Component( int n, bool reduce/* = false */) {
    int i, m;
    this->n = n;
    this->reduce = reduce;

    //DFS
    memset( sign, 0, sizeof sign );
    sn = 0;
    count = 1;

    for( i=0; i<n; i++ )
        if( sign[i] < count )
            DFS( i );
    
    //DFS again
    count = 0;
    memset( flag, -1, sizeof sign );

    if( reduce )
        memset( e_reduced, 0, sizeof e_reduced );

    while( sn-- ) {
        if( flag[st[sn]] == -1 ) {
            RDFS( st[sn] );
            count++;
        }
    }
    m = count;
    if( reduce )
        Reduced( count );

    return m;
}

void Graph::Reduced( int m ) {
    int to;
    count = 2;

    for( int i=0; i<m; i++ ) {

        Edge *t = 0;

        for( Edge *q, *p = e_reduced[i]; p; p = q ) {
            q = p->next;
            to = flag[ p->to ];
            
            if( to != i && sign[to] < count ) {
                sign[to] = count;
                p->to = to;
                p->next = t;
                t = p;
            }
        }

        e_reduced[i] = t;
        count ++;
    }
}


Graph g;
int sign[10000];
int n;

void doit( int m ) {
    int i=0, ans = 0;
    for( i=0; i<n; i++ )
        sign[ g.flag[i] ]++;

    for( i=0; i<m; i++ ) {
        for( Graph::Edge *p = g.e_reduced[i]; p; p=p->next )
            sign[i] = sign[p->to] = 1;
    }

    for( i=0; i<m; i++ )
        if( sign[i] > 1 )
            ans++;
    printf( "%dn", ans );
}

void input( ) {
    int m, a, b;
    g.clear( );
    scanf( "%d%d", &n, &m );
    while( m-- ) {
        scanf( "%d%d", &a, &b );
        a--; b--;
        g.insertEdge( a, b );
    }
}

int main( ) {

    input( );

    doit( g.Strongly_Connected_Component( n, true ) );

    return 0;
}