Cod sursa(job #1038344)

Utilizator pintilie.andreiPintilie pintilie.andrei Data 21 noiembrie 2013 13:08:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <vector>
#define NMAX 100000

using namespace std;

FILE *fin,*fout;

vector <int> M[NMAX],MT[NMAX],v[NMAX];
int use[NMAX],postordine[NMAX],adaugat[NMAX];
int n,m,cat,z,CAT;

void DFS(int);
void DFST(int);

int main()
{
    fin=fopen("ctc.in","r");
    fout=fopen("ctc.out","w");
    int i,k,x,j,dim;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&k,&x);
        M[k].push_back(x);
        MT[x].push_back(k);
    }
    for(i=1;i<=n;i++)
        if(use[i]==0)
        {
            use[i]=1;
            DFS(i);
        }

    for(i=n;i>=1;i--)
        use[i]=0;
    for(i=cat;i>=1;i--)
        if(use[postordine[i]]==0)
        {
            CAT++;
            v[CAT].push_back(postordine[i]);
            use[postordine[i]]=1;
            DFST(postordine[i]);
        }
    fprintf(fout,"%d\n",CAT);
    for(i=1;i<=CAT;i++)
    {
        dim=v[i].size();
        for(j=0;j<dim;j++)
            fprintf(fout,"%d ",v[i][j]);
        fprintf(fout,"\n");
    }
    return 0;
}
void DFST(int x)
{
    int i=0,dim;
    dim=MT[x].size();
    for(i=0;i<dim;i++)
    {   if(use[MT[x][i]]==0)
        {
            use[MT[x][i]]=1;
            DFST(MT[x][i]);
            v[CAT].push_back(MT[x][i]);
        }
    }
}

void DFS(int x)
{
    int i,dim;
    dim=M[x].size();
    for(i=0;i<dim;i++)
    {
        if(use[M[x][i]]==0)
        {
            use[M[x][i]]=1;
            DFS(M[x][i]);
        }
        if(adaugat[i])
        {
            cat++;
            adaugat[x]=1;
            postordine[cat]=x;
        }
    }
    cat++;
    adaugat[x]=1;
    postordine[cat]=x;
}