Cod sursa(job #3243157)

Utilizator TghicaGhica Tudor Tghica Data 16 septembrie 2024 09:28:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <stack>
#include <vector>

#define NMAX 100000

using namespace std;

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

vector<int>edge[NMAX + 1];
stack<int>st;
vector<int>componente[NMAX + 1];
int nrComp;

struct type_node{
  int d, l;
  bool isOnStack;
  vector<int>edge;
}nodes[NMAX + 1];

int timp;

void dfs(int nod) {
  st.push(nod);
  nodes[nod].d = nodes[nod].l = ++timp;
  nodes[nod].isOnStack = 1;
  for(auto copil : edge[nod]) {
    if(nodes[copil].d == 0) {
      dfs(copil);
    }
    if(nodes[copil].isOnStack) {
      nodes[nod].l = min(nodes[nod].l, nodes[copil].l);
    }
  }
  if(nodes[nod].l == nodes[nod].d) {
    nrComp++;
    while(st.top() != nod) {
      componente[nrComp].push_back(st.top());
      nodes[st.top()].isOnStack = 0;
      st.pop();
    }
    componente[nrComp].push_back(st.top());
    nodes[st.top()].isOnStack = 0;
    st.pop();
  }
}

int main() {
  int n, m, a, b;
  cin>>n>>m;
  while(m--) {
    cin>>a>>b;
    edge[a].push_back(b);
  }
  for(int i = 1; i <= n; i++) {
    if(nodes[i].d == 0) {
      dfs(i);
    }
  }
  cout<<nrComp<<"\n";
  for(int i = 1; i <= nrComp; i++) {
    for(int j = 0; j < componente[i].size(); j++) {
      cout<<componente[i][j]<<" ";
    }
    cout<<"\n";
  }
  return 0;
}