Pagini recente » Cod sursa (job #717444) | Cod sursa (job #1297681) | Cod sursa (job #847233) | Cod sursa (job #730850) | Cod sursa (job #376154)
Cod sursa(job #376154)
/*
* 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;
}