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;
}