Cod sursa(job #1156148)

Utilizator thebest001Neagu Rares Florian thebest001 Data 27 martie 2014 14:29:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <stack>
using namespace std;

#define MAX 100001

ifstream in("ctc.in");
ofstream out("ctc.out");

vector<int> normal[MAX], transp[MAX];
stack<int> st;
bool vizN[MAX], vizT[MAX];

vector<int> solutie[MAX];
int solutieN = 0;
void DFS(int x) {
  vizN[x] = true;
  for (vector<int>::iterator i = normal[x].begin(); i != normal[x].end(); i++) {
    if (!vizN[*i]) {
      DFS(*i);
    }
  }
  st.push(x);
}

void DFST(int x){
  vizT[x] = true;
  solutie[solutieN].push_back(x);
  for (vector<int>::iterator i = transp[x].begin(); i != transp[x].end(); i++) {
    if (!vizT[*i]) {
      DFST(*i);
    }
  }
}

int main() {
  int n, k;
  in>>n>>k;
  for (int i = 1; i <= k; i++) {
    int x, y;
    in>>x>>y;
    normal[x].push_back(y);
    transp[y].push_back(x);
  }

  for (int i = 1; i <= n; i++) {
    if (!vizN[i])
      DFS(i);
  }



  while (!st.empty()) {
    int x = st.top();
    st.pop();
    if (!vizT[x]) {
      ++solutieN;
      DFST(x);
    }
  }

  out<<solutieN<<"\n";
  for (int i = 1; i <= solutieN; i++){
    for (vector<int>::iterator j = solutie[i].begin(); j != solutie[i].end(); j++) {
      out<<*j<<" ";
    }
    out<<"\n";
  }

  return 0;
}