Cod sursa(job #1896052)

Utilizator rusucatalinRusu Vasile Catalin rusucatalin Data 28 februarie 2017 13:30:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#define NMAX 100002

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector <int> G[NMAX];
vector <int> GT[NMAX];

vector <int> CTC[NMAX];

int nr;
int n, m;
int postordine[NMAX];
int poz;
bool uz[NMAX];

void citire();
void DFS(int k);
void DFST(int k);
void afisare();

int main()
{
int i;
citire();
for (i=1;i<=n;i++)
     if (!uz[i])
         DFS(i);
for (i=n;i>=1;i--)
     if (uz[postordine[i]])
         {
          nr++;
          DFST(postordine[i]);
         }
afisare();
fin.close();
fout.close();
return 0;
}

void afisare()
    {
     int i;
     int j;
     int lg;
     fout<<nr<<'\n';
     for (i=1;i<=nr;i++)
        {
         lg=CTC[i].size();
         for (j=0;j<lg;j++)
              fout<<CTC[i][j]<<' ';
         fout<<'\n';
        }
    }

void DFST(int k)
    {
     int i;
     int lg=GT[k].size();
     uz[k]=0;
     CTC[nr].push_back(k);
     for (i=0;i<lg;i++)
          if (uz[GT[k][i]])
              DFST(GT[k][i]);
    }

void DFS(int k)
    {
     int i;
     int lg=G[k].size();
     uz[k]=1;
     //parcurg lista de adiacenta al lui x
     for (i=0;i<lg;i++)
          if (!uz[G[k][i]])
              DFS(G[k][i]);
     postordine[++poz]=k;
    }

void citire()
    {
     int i;
     int x, y;
     fin>>n>>m;
     for (i=1;i<=m;i++)
         {
          fin>>x>>y;
          G[x].push_back(y);
          GT[y].push_back(x);
         }
    }