Cod sursa(job #2928603)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 23 octombrie 2022 14:46:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

const int NMAX = 1e5;

vector <int> graf[NMAX + 1], revgraf[NMAX + 1];
vector <int> viz[NMAX + 1];
vector <int> ctcorder;
bool marked[NMAX + 1];

void dfs (vector<int>* graf, int node, vector<int>& viz){
  marked[node] = 1;
  int _Size = graf[node].size();
  for (int i = 0; i < _Size; i++){
    if (!marked[graf[node][i]])
      dfs(graf, graf[node][i], viz);
  }

  viz.push_back(node);
}

int main(){

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

  int n, m;

  fin >> n >> m;
  for (int i = 0; i < m; i++){
    int a, b;
    fin >> a >> b;
    graf[a].push_back(b);
    revgraf[b].push_back(a);
  }

  for (int i = 1; i <= n; i++){
    if (!marked[i])
      dfs (graf, i, ctcorder);
  }

  memset (marked, 0, sizeof(marked));

  int nrofcomp = 0;
  int currnode;
  while (!ctcorder.empty()){
    currnode = ctcorder.back();
    ctcorder.pop_back();
    if (!marked[currnode]){
      dfs (revgraf, currnode, viz[nrofcomp]);
      ++nrofcomp;
    }
  }

  fout << nrofcomp << "\n";
  for (int i = 0; i < nrofcomp; i++){
    int size_ = viz[i].size();
    for (int node = 0; node < size_; node ++)
      fout << viz[i][node] << " ";
    fout << "\n";
  }
  return 0;
}