# Poj Solution 1515

```http://poj.org/problem?id=1515

#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 %dn", 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( "%dnn", i++ );
doit();
printf( "#n" );
}

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.