Cod sursa(job #3207529)

Utilizator TghicaGhica Tudor Tghica Data 26 februarie 2024 12:57:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define NMAX 100000

using namespace std;

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

struct type_node{
  int d, l, onStack;
  vector<int>edge;
}graf[NMAX + 1];

int globalTime, nrComp;
vector<int>comp[NMAX + 1];

int stiva[NMAX + 1], k;

void dfs(int nod) {
  int momStiva = k;
  k++;
  stiva[k] = nod;
  graf[nod].onStack = 1;
  globalTime++;
  graf[nod].d = graf[nod].l = globalTime;
  for(auto copil : graf[nod].edge) {
    if(graf[copil].d == 0) {
      dfs(copil);
    } if(graf[copil].onStack == 1)
     graf[nod].l = min(graf[nod].l, graf[copil].l);
  }
  if(graf[nod].l == graf[nod].d) {
    nrComp++;
    while(stiva[k] != nod) {
      graf[stiva[k]].onStack = 0;
      comp[nrComp].push_back(stiva[k--]);
    }
    graf[stiva[k]].onStack = 0;
    comp[nrComp].push_back(stiva[k--]);
  }
}

signed main() {
  int n, m, a, b;
  cin>>n>>m;
  while(m--) {
    cin>>a>>b;
    graf[a].edge.push_back(b);
  }
  for(int i = 1; i <= n; i++) {
    if(graf[i].d == 0)
      dfs(i);
  }
  cout<<nrComp<<"\n";
  while(nrComp--) {
    for(auto nod : comp[nrComp + 1]){
      cout<<nod<<" ";
    }
    cout<<"\n";
  }
  return 0;
}