Cod sursa(job #1232392)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 22 septembrie 2014 19:53:23
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005

using namespace std;

bool viz[NMAX];
int timp[NMAX], nr;
vector<int> v[NMAX];
vector<int> v2[NMAX];
vector<int> p;
vector<int> sol[NMAX];

void DFS(int x, int t) {
  ++t;
  viz[x] = 1;
  int size = v[x].size();
  for(int i = 0; i < size; ++i) {
    if(!viz[v[x][i]]) {
      DFS(v[x][i], t);
    }
  }
  timp[x] = ++t;
}

bool cmp(int i, int j) {
  return timp[i] > timp[j];
}

void DFS_inv(int x) {
  viz[x] = 1;
  p.push_back(x);
  int size = v2[x].size();
  for(int i = 0; i < size; ++i) {
    if(!viz[v2[x][i]]) {
      DFS_inv(v2[x][i]);
    }
  }
  int sizep = p.size();
  for(int i = 0; i < sizep; ++i)
    sol[nr].push_back(p[i]);
  p.clear();
}


int main ()
{
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");
  int n, m, x, y;
  cin >> n >> m;
  for(int i = 1; i <= m; ++i) {
      cin >> x >> y;
      v[x].push_back(y);
      v2[y].push_back(x);
  }
  for(int i = 1; i <= n; ++i)
    if(!viz[i]) {
      DFS(i, 1);
      }
  for(int i = 1; i <= n; ++i)
      viz[i] = 0;
  for(int i = 1; i <= n; ++i)
      sort(v2[i].begin(), v2[i].end(), cmp);
  for(int i = 1; i <= n; ++i)
      if(!viz[i]) {
         ++nr;
        DFS_inv(i);
      }
   cout << nr << '\n';
   for(int i = 1; i <= nr; ++i, cout << '\n')
      for(int j = 0; j < sol[i].size(); ++j)
         cout << sol[i][j] << ' ';
  return 0;
}