Cod sursa(job #3243145)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 16 septembrie 2024 09:01:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

const int nmax = 1e5;

vector <int> graf[nmax + 1];
vector <int> revgraf[nmax + 1];
vector <int> ctc;
vector <int> viz[nmax + 1];

int ctcnr;
bool marked[nmax + 1];
void dfs (vector <int> *graf, int node, vector<int>& viz){
  marked[node] = true;
  for (auto neighbour : graf[node]){
    if (!marked[neighbour])
      dfs (graf, neighbour, viz);
  }
  viz.push_back(node);
}

int main(){

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

  int n, m;
  fin >> n >> m;

  for (int i = 1; i <= m; i++){
    int x, y;
    fin >> x >> y;

    graf[x].push_back(y);
    revgraf[y].push_back(x);
  }

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

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

  while (!ctc.empty()){
    int topnode = ctc.back();
    ctc.pop_back();

    if (!marked[topnode]){
      dfs (revgraf, topnode, viz[ctcnr]);
      ctcnr ++;
    }
  }

  fout << ctcnr << "\n";
  while (ctcnr--){
    for (auto sol: viz[ctcnr]){
      fout << sol << " ";
    }
    fout << "\n";
  }
  return 0;
}