Cod sursa(job #2354517)

Utilizator OtiliaTurcanu1Turcanu Otilia OtiliaTurcanu1 Data 25 februarie 2019 12:47:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>

#include <vector>

#define NMAX 100002



using namespace std;

ifstream fin("ctc.in");

ofstream fout("ctc.out");



int n, nr, nrc;

vector<int> G[NMAX];

vector<int> GT[NMAX];

vector<int> CTC[NMAX];

int postordine[NMAX];

bool uz[NMAX];

void citire();

void afisare();

void DFS(int x);

void DFST(int x);



int main()

{int i;

  citire();

  ///etapa I

  for (i=1; i<=n; i++)

      if (!uz[i]) DFS(i);

  ///etapa II

  ///uz[i]=1 pentru varfurile nevizitate in DFST

  ///0 altfel

  for (i=n; i>0; i--)

      if (uz[postordine[i]])

          {nrc++; DFST(postordine[i]);}

  afisare();

  return 0;

}



void citire()

{int i, x, y, m;

 fin>>n>>m;

 for (i=0; i<m; i++)

      {//arc

       fin>>x>>y;

       G[x].push_back(y);

       ///in graful transpus pun arcul (y,x)

       GT[y].push_back(x);

      }

}



void DFS(int x)

{int i;

 uz[x]=1;

 for (i=0; i<G[x].size(); i++)

     if (uz[G[x][i]]==0)

        DFS(G[x][i]);

 nr++;

 postordine[nr]=x;

}



void DFST(int x)

{int i;

 uz[x]=0;

 CTC[nrc].push_back(x);

 for (i=0; i<GT[x].size(); i++)

     if (uz[GT[x][i]])

        DFST(GT[x][i]);

}



void afisare()

{int i, j;

 fout<<nrc<<'\n';

 for (i=1; i<=nrc; i++)

      {

       for (j=0; j<CTC[i].size(); j++)

            fout<<CTC[i][j]<<' ';

       fout<<'\n';

      }

}