Cod sursa(job #1250458)

Utilizator Lucian_BosinceanuLucian-Andrei Bosinceanu Lucian_Bosinceanu Data 28 octombrie 2014 10:05:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
//#include <fstream>
#include <cstdio>
#include <vector>
#define DMAX 100005

using namespace std;

FILE*fin=fopen("ctc.in","r");
FILE*fout=fopen("ctc.out","w");

void citire();
void rezolvare();
void DFSG(int vf);
void DFST(int vf);
void clear();
void afisare();

vector <int> G[DMAX];
vector <int> T[DMAX];
vector <int> sol[DMAX];
int n,m,nrctc,pozpo;
int uz[DMAX];
int postord[DMAX];

int main()
{
citire();
rezolvare();
afisare();
    return 0;
}

void citire()
{
int i,x,y;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
     {
      fscanf(fin,"%d %d",&x,&y);
      G[x].push_back(y);
      T[y].push_back(x);
     }
}

void rezolvare()
{
int i;
for (i=1;i<=n;i++)
     if (uz[i]==0) DFSG(i);
clear();
for (i=n;i>=1;i--)
     if(uz[postord[i]]==0)
        {
        nrctc++;
        DFST(postord[i]);
        }
}

void clear()
{
int i;
for (i=1;i<=n;i++) uz[i]=0;
}

void DFSG(int vf)
{
int i;
uz[vf]=1;
for (i=0;i<G[vf].size();i++)
     if (uz[ G[vf][i] ]==0) DFSG(G[vf][i]);
postord[++pozpo]=vf;
}

void DFST(int vf)
{
int i;
sol[nrctc].push_back(vf);
uz[vf]=1;
for (i=0;i<T[vf].size();i++)
     if ( uz[ T[vf][i] ]==0) DFST(T[vf][i]);
}

void afisare()
{
int i,j;
fprintf(fout,"%d\n",nrctc);
for (i=1;i<=nrctc;i++)
     {for (j=0;j<sol[i].size();j++)
          fprintf(fout,"%d ",sol[i][j]);
     fprintf(fout,"\n");
     }
}