Cod sursa(job #3296197)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 12 mai 2025 09:57:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 100000;

vector<int> g[MAXN + 1], stk, noduri[MAXN + 1];
int low[MAXN + 1], poz[MAXN + 1], instack[MAXN + 1], ctc, ptr;

void addNode() {
  int node = stk.back();
  stk.pop_back();
  instack[node] = 0;
  noduri[ctc].push_back(node);
}

void dfs(int node) {
  instack[node] = 1;
  stk.push_back(node);
  low[node] = poz[node] = ++ptr;

  for(int vecin : g[node]) {
    if(!poz[vecin]) {
      dfs(vecin);
      low[node] = min(low[node], low[vecin]);
    } else if(instack[vecin]) {
      low[node] = min(low[node], low[vecin]);
    }
  }

  if(low[node] == poz[node]) {
    ctc++;
    while(stk.back() != node) {
      addNode();
    }
    addNode();
  }
}

int main() {
  int n, m;
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    fin >> u >> v;
    g[u].push_back(v);
  }

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

  fout << ctc << "\n";
  for(int i = 1; i <= ctc; i++) {
    for(int nod : noduri[i]) {
      fout << nod << " ";
    }
    fout << "\n";
  }

  return 0;
}