Cod sursa(job #3374724)

Utilizator MasterFire1990Balaban Nicolae Adrian MasterFire1990 Data 9 noiembrie 2026 09:44:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
vector<int> a[100001], st;
vector<vector<int>> res;
int id[100001], low[100001], T;
bool in[100001];
void dfs(int u) {
  id[u] = low[u] = ++T;
  st.push_back(u);
  in[u] = 1;
  for (int w : a[u]) {
    if (!id[w]) {
      dfs(w);
      low[u] = min(low[u], low[w]);
    } else if (in[w])
      low[u] = min(low[u], id[w]);
  }
  if (low[u] == id[u]) {
    vector<int> c;
    int w;
    do {
      w = st.back();
      st.pop_back();
      in[w] = 0;
      c.push_back(w);
    } while (w != u);
    res.push_back(c);
  }
}
int main() {
  ifstream f("ctc.in");
  ofstream g("ctc.out");
  int n, m;
  f >> n >> m;
  while (m--) {
    int x, y;
    f >> x >> y;
    a[x].push_back(y);
  }
  for (int i = 1; i <= n; i++)
    if (!id[i])
      dfs(i);
  g << res.size() << "\n";
  for (auto &c : res) {
    for (int x : c)
      g << x << " ";
    g << "\n";
  }
}