Cod sursa(job #374674)

Utilizator cristikIvan Cristian cristik Data 17 decembrie 2009 20:00:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#define max 100010
int stack[max],ind[max],low[max],i,j,n,m,k,index,top,comp;
char s[max];
struct lista
{
    int nod;
    lista *next;
};
lista *g[max],*q[max],*p;
void push(lista *&g,int j)
{
    lista *p=new lista;
    p->nod=j;
    p->next=g;
    g=p;
}
void dfs(int v)//tarjan
{
    int w; lista *p;
    ind[v]=low[v]=++index;
    stack[++top]=v;
    for(p=g[v]; p!=NULL; p=p->next)
     if(!s[p->nod])
     {
         if(!ind[p->nod]) dfs(p->nod);
         if(low[p->nod]<low[v]) low[v]=low[p->nod];
     }
    if(low[v]==ind[v])
    {
        comp++;
        while(stack[top]!=v)
        {
            s[stack[top]]=1;
            push(q[comp],stack[top]);
            top--;
        }
        push(q[comp],v);
        s[v]=1;
        top--;
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(k=1; k<=m; k++)
    {
        scanf("%d%d",&i,&j);
        push(g[i],j);
    }
    for(i=1; i<=n; i++)
     if(!ind[i]) dfs(i);
    printf("%d\n",comp);
    for(i=1; i<=comp; i++)
    {
        for(p=q[i]; p!=NULL; p=p->next)
         printf("%d ",p->nod);
        printf("\n");
    }
    return 0;
}