Cod sursa(job #754883)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 3 iunie 2012 21:40:21
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb

#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector<int> *Muchii;

stack<int> S;
long Time;
long Out[200010];
long Outp;
long D[100005];
long Low[100005];
long Count;

long N,M;

void tarjan(long p)
{
 long a,b,c;
 D[p] = Time;
 Low[p] = Time;
 Time += 1;
 S.push(p);
 for (a = 0;a < Muchii[p].size();a += 1)
  {
   b = Muchii[p][a];
   if (D[b] == 0)
     {
      tarjan(b);
      if (Low[b] < Low[p])
        {
         Low[p] = Low[b];
        }
     }
    else
     {
      if (D[b] < Low[p])
        {
         Low[p] = D[b];
        }
     }
  }
 if (Low[p] == D[p])
   {
    Count += 1;
    while (S.top() != p)
     {
      Out[Outp] = S.top();
      Outp += 1;
      S.pop();
     }
    Out[Outp] = S.top();
    Outp += 1;
    S.pop();
    Out[Outp] = 0;
    Outp += 1;
   }
}

int main(void)
{
 long i,a,b;
 fstream fin("ctc.in",ios::in);
 fstream fout("ctc.out",ios::out);
 fin >> N >> M;
 Muchii = new vector<int>[N + 5];
 for (i = 0;i < N;i += 1)
  {
   Muchii[i].reserve(20);
  }
 for (i = 0;i < M;i += 1)
  {
   fin >> a >> b;
   Muchii[a].push_back(b);
  }
 Time = 1;
 for (i = 1;i <= N;i += 1)
  {
   if (D[i] == 0)
     {
      tarjan(i);
     }
  }
 fout << Count << "\n";
 for (i = 0;i < Outp;i += 1)
  {
   if (Out[i] == 0)
     {
      fout << "\n";
     }
    else
     {
      fout << Out[i] << " ";
     }
  }
 fin.close();
 fout.close();
 return 0;
}