Cod sursa(job #1648268)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 11 martie 2016 09:10:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

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

vector <int> L[100009], H[100009];
vector <int> sol[100009];
int N, M, nrsol, top, st[100009];
bool viz[100009];

void Citire()
{
   int x, y, i;

   fin >> N >> M;
   for (i=1; i<=M; i++)
   {
      fin >> x >> y;
      L[x].push_back(y);
      H[y].push_back(x);
   }
}

void DFS(int k)
{
   int i, j;
   viz[k] = 1;
   
   for (j=0; j<L[k].size(); j++)
   {
      i = L[k][j];
      if (!viz[i]) DFS(i);
   }
   st[++top] = k;
}

void DFS2(int k)
{
   int i, j;
   viz[k] = 1;
   
   for (j=0; j<H[k].size(); j++)
   {
      i = H[k][j];
      if (!viz[i]) DFS2(i);
   }
   sol[nrsol].push_back(k);
}

void Rezolva()
{
   int i, j, nod;
   top = 0;
   for (i=1; i<=N; i++)
       if (!viz[i]) DFS(i);
   
   for (i=1; i<=N; i++)
       viz[i] = 0;    

   while (top > 0)
   {
     nod = st[top--];
     if (!viz[nod]) 
     {
         nrsol++;
         DFS2(nod);
     }
   }
}

void Afisare()
{
   int i, j;
   fout << nrsol << "\n";
   for (i=1; i<=nrsol; i++)
   {
      for (j=0; j<sol[i].size(); j++)
        fout << sol[i][j] << " ";
     fout << "\n";
   }
}


int main ()
{
  Citire();
  Rezolva();
  Afisare();
  fin.close();
  fout.close();
  return 0;
}