1515.txt

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

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

bool e[1000][1000];
int low[1000];
int visit[1000];
int vs,n;

void print( int a, int b)
{
	printf( "%d %d\n", a+1, b+1 );
}

void search( int s, int f )
{
	int i;
		
	visit[s] = vs++;
	low[s] = visit[s];

	for( i=0; i<n; i++ )
	if( e[s][i] && i != f )
	{
		if( visit[i] == 0 )
		{
			search( i, s );
	
			if( low[i] > visit[s] )
			{
				print(s,i);
				print(i,s);
			
				e[s][i] = e[i][s] = false;
			}
		}

		if( low[i] < low[s] ) low[s] = low[i];
	}
	
}

bool connect[1000];

void find_path( int s )
{
	int i;

	if( connect[s] ) return ;
	
	connect[s] = true;

	for( i=0; i<n; i++ )
	if( e[s][i] )
	{
		e[i][s] = e[s][i] = false;
		print( s, i );

		find_path( i ) ;
	}

	return ;
}

bool init()
{
	int i, j, m;

	scanf( "%d %d", &n, &m );

	if( n == 0 && m == 0 ) return false;

	memset( e, 0, sizeof(e) );
	memset( visit, 0, sizeof(visit) );
	memset( low, 0, sizeof(low) );
	memset( connect, 0, sizeof(connect) );

	vs=1;

	while( m-- )
	{
		scanf( "%d %d", &i, &j );

		if( i == j ) print( i, i );
		else e[i-1][j-1] = e[j-1][i-1] = true;
	}

	return true;
}

void doit()
{
	int i, j;

	search( 0, -1 );

	for( i=0; i<n; i++ )
	if( !connect[i] )
	{
		find_path( i ) ;
	}

	return ;
}


int main()
{
	int i=1;
	
	while( init() )
	{
		printf( "%d\n\n", i++ );
		doit();
		printf( "#\n" );
	}

	return 0;
}