Cod sursa(job #376154)

Utilizator alexandru92alexandru alexandru92 Data 20 decembrie 2009 20:56:17
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
/*
 * File:   main.c
 * Author: virtualdemon
 *
 * Created on December 20, 2009, 7:42 PM
 */
#include <cstdio>
#include <cstdlib>
#define minim( x, y ) x < y ? x : y

/*
 *
 */
int counting, indecs;
int *uz, *lowlink, *idx;
struct vertex
{
    int info;
    vertex* next;
} **L, *S, **tc;
typedef vertex* list;
inline void push( list& f, int x ) //insert a new vertex in the list
{
    list q=(list)malloc( sizeof(vertex) );
    q->info=x;
    q->next=f;
    f=q;
}
inline void pop( list& f )
{
    list q=f;
    f=f->next;
    free(q);
}
inline int top( list f )
{
    return f->info;
}
void DFS( int x )
{++indecs;
    idx[x]=lowlink[x]=indecs;
    uz[x]=1;
    push( S, x );
    for( list p=L[x]; p; p=p->next )
        if( !idx[p->info] )
        {
            DFS(p->info);
            lowlink[x]=minim( lowlink[x], lowlink[p->info] );
        }
        else if( uz[p->info] )
               lowlink[x]=minim( lowlink[x], lowlink[p->info] );
    if( lowlink[x] == idx[x] )
    {int nod;
        ++counting;
        tc=(list*)realloc( (void*)tc, counting*sizeof(list) );
        do
        {nod=top(S);
            uz[nod]=0;
            push( tc[counting-1], nod+1 );
            pop(S);
        }while( nod != x );
    }
}
int main()
{int n, m, x, y, i;
    freopen( "ctc.in", "rt", stdin );
    scanf("%d%d", &n, &m);
    L=(list*)malloc( n*sizeof(list) );
    uz=(int*)calloc( n, sizeof(int) );
    lowlink=(int*)calloc( n, sizeof(int) );
    idx=(int*)calloc( n, sizeof(int) );
    while( m-- )
    {
        scanf("%d%d", &x, &y );
        push( L[x-1], y-1 );
    }
    for( i=0; i < n; ++i )
        if( !idx[i] )
            DFS(i);
    freopen( "ctc.out", "wt", stdout );
    printf("%d\n", counting);
    for( i=0; i < counting; ++i )
    {
        for( list p=tc[i]; p; p=p->next )
            printf("%d ", p->info );
        printf("\n");
    }
    return 0;
}