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