Cod sursa(job #236044)

Utilizator DastasIonescu Vlad Dastas Data 26 decembrie 2008 17:46:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>

const int maxn = 100001;

FILE *in = fopen("ctc.in", "r"), *out = fopen("ctc.out", "w");

struct graf
{
    int nod;

    graf *next;
};

int n, m;
graf *a[maxn], *at[maxn], *comp[maxn];
int viz[maxn], pord[maxn], k, nrc;

void add(int what, graf *&list)
{
    graf *t = new graf;
    t->nod = what;
    t->next = list;
    list = t;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    int x, y;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d", &x, &y);

        add(y, a[x]);
        add(x, at[y]);
    }

}

void df(int nod)
{
    if ( viz[nod] )
        return;
    viz[nod] = 1;

    graf *t = a[nod];

    while ( t )
    {
        df(t->nod);

        t = t->next;
    }

    pord[++k] = nod;
}

void dfT(int nod)
{
    if ( !viz[nod] )
        return;
    viz[nod] = 0;
    add(nod, comp[nrc]);

    graf *t = at[nod];

    while ( t )
    {
        dfT(t->nod);

        t = t->next;
    }
}

int main()
{
    read();

    for ( int i = 1; i <= n; ++i )
        df(i);

    for ( int i = n; i; --i )
        if ( viz[ pord[i] ] )
        {
            ++nrc;
            dfT( pord[i] );
        }

    fprintf(out, "%d\n", nrc);
    for ( int i = 1; i <= nrc; ++i )
    {
        graf *t = comp[i];

        while ( t )
        {
            fprintf(out, "%d ", t->nod);

            t = t->next;
        }

        fprintf(out, "\n");
    }

    return 0;
}