Cod sursa(job #2331146)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 29 ianuarie 2019 11:07:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <string.h>
using namespace std;

#define NMAX 100005

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

int n, m, i, k, nrctc, viz[NMAX], st[NMAX];

struct nod {
    int inf;
    nod* urm;
} *l[NMAX], *lt[NMAX], *sol[NMAX];

void adaug_nod(nod* &l, int x) {
    nod* p = new nod;

    p->inf = x;
    p->urm = l;
    l = p;
}

void citire() {
    int x, y;

    fscanf(f, "%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        fscanf(f, "%d%d", &x, &y);
        adaug_nod(l[x], y);
        adaug_nod(lt[y], x);
    }
}

void df1(int i) {
    nod *c;

    viz[i] = 1;

    for(c = l[i]; c != NULL; c = c->urm)
      if (!viz[c->inf]) df1(c->inf);

    st[++k]=i;
}


void df2(int i) {
    nod *c;

    viz[i]=1;
    adaug_nod(sol[nrctc], i);

    for(c=lt[i]; c != NULL; c=c->urm)
      if (!viz[c->inf]) df2(c->inf);
}

void afisare() {
    fprintf(g, "%d\n", nrctc);

    for(int i = 1; i <= nrctc; i++) {
        for(nod* p = sol[i]; p != NULL; p = p->urm) fprintf(g, "%d ", p->inf);
        fprintf(g, "\n");
    }
}

int main() {

    citire();

    for(i = 1; i <= n; i++)
        if (!viz[i]) df1(i);

    memset (viz, 0, sizeof(viz));

    for(i = n; i >= 1; i--)
        if (!viz[st[i]]) {
            nrctc++; df2(st[i]);
        }

    afisare();

    fclose(f); fclose(g);

    return 0;
}