3180.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3180  User Id:fzk 
Memory:1196K  Time:61MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", 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;
}