Cod sursa(job #2145240)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 27 februarie 2018 10:53:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<bits/stdc++.h>
using namespace std;

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

int n,m,viz[100005],st[100005],k,i,s;

struct nod {
    int inf;
    nod* urm;
} *L[100005],*Lt[100005],*sol[100005];

void adaug(nod*& l, int x) {
    nod* c=new nod;
    c->urm=l; c->inf=x;
    l=c;
}

void citire() {
    int i,x,y;

    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++) {
        fscanf(f,"%d%d",&x,&y);
        adaug(L[x],y); adaug(Lt[y],x);
    }
}

void df1(int x) {
    nod* c;
    viz[x]=1;
    for(c=L[x];c;c=c->urm)
        if(!viz[c->inf]) df1(c->inf);
    st[++k]=x;
}

void df2(int x) {
    nod* c;
    viz[x]=1;
    adaug(sol[s],x);
    for(c=Lt[x];c;c=c->urm)
        if(!viz[c->inf]) df2(c->inf);
}

void afis() {
    int i;
    nod* c;

    fprintf(g,"%d\n",s);
    for(i=1;i<=s;i++) {
        for(c=sol[i];c;c=c->urm) fprintf(g,"%d ",c->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]]) {
            s++;
            df2(st[i]);
        }
    afis();

    fclose(f); fclose(g);

    return 0;
}