Cod sursa(job #804737)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 30 octombrie 2012 11:44:42
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#define MAXN 1001

using namespace std;

struct nod { int inf; nod* next;};

int n, m, nr, c;
nod* v[MAXN];
nod* vt[MAXN];
int postord[MAXN], viz[MAXN], con[MAXN];

void init () {
    for (int i=1; i<=n; ++i)
        v[i] = vt[i] = NULL;
}

void v_push (int x, int y) {
    nod* p;
    p = new nod;
    p->inf = y;
    p->next = v[x];
    v[x] = p;
}

void vt_push (int x, int y) {
    nod* p;
    p = new nod;
    p->inf = y;
    p->next = vt[x];
    vt[x] = p;
}

void read () {
    freopen ("ctc.in", "r", stdin);
    scanf ("%d%d", &n, &m);
    init ();
    int i, x, y;
    for (i=1; i<=m; ++i) {
        scanf ("%d%d", &x, &y);
        v_push (x, y);
        vt_push (y, x);
    }
}

void DFST (int x) {
    viz[x] = 0;
    con[x] = c;
    nod* p; p = new nod;
    p = vt[x];
    while (p) {
        if (viz[p->inf])
            DFST(p->inf);
        p = p->next;
    }
}

void DFS (int x) {
    viz[x] = 1;
    nod* p; p = new nod;
    p = v[x];
    while (p) {
        if (viz[p->inf] == 0)
            DFS (p->inf);
        p = p->next;
    }
    postord[++nr] = x;
}

void write () {
    freopen ("ctc.out", "w", stdout);
    int i, j;
    printf ("%d\n", c);
    for (i=1; i<=c; ++i) {
        for (j=1; j<=n; ++j)
            if (con[j] == i)
                printf ("%d ", j);
        printf ("\n");
    }
    fclose (stdout);
}

int main () {
    int i;
    read ();
    for (i=1; i<=n; ++i)
        if (viz[i] == 0) DFS(i);
    for (i=n; i>0; --i)
        if (viz[postord[i]]) {
            ++c;
            DFST (postord[i]);
        }
    write ();
    return 0;
}