Cod sursa(job #1233070)

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

using namespace std;

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


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

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

void DFS_inv(int x) {
  viz[x] = 1;
  p.push_back(x);
  for(int i = 0; i < v2[x].size(); ++i) {
      //cout << "vecin al lui " << x << ": " << v2[x][i] << '\n';
    if(!viz[v2[x][i]]) {
      DFS_inv(v2[x][i]);
    }
  }
}


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);
      }
  for(int i = 1; i <= n; ++i)
      viz[i] = 0;
  for(int i = n; i >= 1; --i)
      if(!viz[timp[i]]) {
        DFS_inv(timp[i]);
        int sizep = p.size();
        if(sizep)
            ++nr;
        for(int i = 0; i < sizep; ++i)
          sol[nr].push_back(p[i]);
        p.clear();
      }
   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;
}