Cod sursa(job #347177)

Utilizator aghamatMorariu Razvan aghamat Data 11 septembrie 2009 12:39:55
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#define DIM 100005
struct Nod{
    int x;
    Nod *adr;};
Nod *graf[DIM], *graft[DIM], *sol[DIM];
int n, m, viz[DIM], postviz[DIM], l, nr;

void add(Nod *&p, int k)
{
    Nod *q;
    q=new Nod;
    q->adr=p;
    q->x=k;
    p=q;
    }

void df(int k)
{
    Nod *p;
    viz[k]=1;
    for (p=graf[k]; p; p=p->adr)
        if (!viz[p->x])
            df(p->x);
    postviz[++l]=k;
    }

void dft(int k)
{
    Nod *p;
    viz[k]=0;
    add(sol[nr], k);
    for (p=graft[k]; p; p=p->adr)
        if (viz[p->x])
            dft(p->x);
    }

void afisare()
{
    Nod *p;
    int k;
    printf("&d\n", nr);
    for ( k=1; k<=nr; ++k)
    {
        for (p=sol[k]; p; p=p->adr)
            printf("%d ", p->x);
        printf("\n");
        }
    }

int main()
{
    int x, y;
    
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        add(graf[x],y);
        add(graft[y],x);
        }
    
    for (int i=1; i<=n; ++i)
        if (!viz[i])
            df(i);
    for (int i=n; i; --i)
        if (viz[postviz[i]])
        {
            ++nr;
            dft(i);
            }
    afisare();
    return 0;
    }