Cod sursa(job #274414)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 9 martie 2009 18:33:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <memory>

using namespace std;

struct nod {int inf; nod *urm;} *g[100001],*gt[100001],*l[100001];
int viz[100001],st[100001];
int n,m,nr;

void baga(int x, int y)
{
    nod *q=new nod;
    q->inf=y;
    q->urm=g[x];
    g[x]=q;
    q=new nod;
    q->inf=x;
    q->urm=gt[y];
    gt[y]=q;
}

void parc1(int x)
{
    viz[x]=1;
    for(nod *q=g[x];q;q=q->urm)
        if(!viz[q->inf])
            parc1(q->inf);
    st[++st[0]]=x;
}

void parc2(int x)
{
    viz[x]=1;
    nod *q=new nod;
    q->inf=x;
    q->urm=l[nr];
    l[nr]=q;
    for(q=gt[x];q;q=q->urm)
        if(!viz[q->inf])
            parc2(q->inf);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        baga(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            parc1(i);
    memset(viz,0,sizeof(viz));
    for(int i=n;i>0;i--)
        if(!viz[st[i]])
        {
            nr++;
            parc2(st[i]);
        }
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++)
    {
        for(nod *q=l[i];q;q=q->urm)
            printf("%d ",q->inf);
        printf("\n");
    }
    return 0;
}