Cod sursa(job #1038353)

Utilizator pintilie.andreiPintilie pintilie.andrei Data 21 noiembrie 2013 13:22:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <vector>
#define NMAX 100010

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)
        {
            DFS(i);
        }

    for(i=n;i>=1;i--)
        use[i]=0;
    for(i=cat;i>=1;i--)
        if(use[postordine[i]]==0)
        {
            CAT++;
            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;
    use[x]=1;
    dim=MT[x].size();
    for(i=0;i<dim;i++)
    {   if(use[MT[x][i]]==0)
        {
            DFST(MT[x][i]);
        }
    }
    v[CAT].push_back(x);
}

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]);
        }
    }
    cat++;
    postordine[cat]=x;
}