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

```
This entry was posted in poj. Bookmark the permalink.