Cod sursa(job #1233059)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 24 septembrie 2014 16:43:56
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005

using namespace std;

bool viz[NMAX];
int timp[NMAX], nr, n;
vector<int> v[NMAX];
vector<int> v2[NMAX];
vector<int> p;
vector<int> sol[NMAX];
int f[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();
  if(sizep)
      ++nr;
  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 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)
      f[i] = i;
  sort(f + 1, f + n + 1, cmp);
  for(int i = 1; i <= n; ++i)
      if(!viz[i]) {
        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;
}