Cod sursa(job #2041842)

Utilizator CriogeniXBociat Daniel Tiberiu CriogeniX Data 17 octombrie 2017 20:17:19
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMax = 100000;
vector <int> G[NMax + 5], GT[NMax + 5],CTC[NMax + 5];
int N,M,NrCTC,Use[NMax + 5];
void Read()
{
  fin >> N >> M;
  for(int i = 1; i <= M; ++i)
  {
    int x,y;
    fin >> x >> y;
    G[x].push_back(y);
    GT[y].push_back(x);
  }
}

void DFSP(int Nod)
{
  Use[Nod] = 1;
  for(int i = 0; i < (int)G[Nod].size(); ++i)
  {
    int Vecin = G[Nod][i];
    if(Use[Vecin] == 0)
      DFSP(Vecin);
  }
}
void DFSM(int Nod)
{
  Use[Nod] = 2;CTC[NrCTC].push_back(Nod);
  for(int i = 0; i < (int)GT[Nod].size(); ++i)
  {
    int Vecin = GT[Nod][i];
    if(Use[Vecin] == 1)
      DFSM(Vecin);
  }
}

void Reset()
{
  for(int i = 1; i <= N; ++i)
    if(Use[i] == 1)
      Use[i] = 0;
}

void Solve()
{
  for(int i = 1; i <= N; ++i)
  {
    if(Use[i] == 0)
    {
      NrCTC++;
      DFSP(i);
      DFSM(i);
      Reset();
    }
  }
}

void Print()
{
  fout << NrCTC<< "\n";
  for(int i = 1; i <= NrCTC; ++i)
  {
    for(int j = 0; j < (int)CTC[i].size(); ++j)
      fout << CTC[i][j] << " ";
    fout << "\n";
  }
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}