Cod sursa(job #3196945)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 24 ianuarie 2024 23:53:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 1e5;

bool vis[NMAX + 1];

std::vector<int> order, cur;
std::vector<int> g[NMAX + 1], gg[NMAX + 1];

void dfs0(int u) {
  vis[u] = true;
  for (const auto &v : g[u]) {
    if (!vis[v]) {
      dfs0(v);
    }
  }
  order.push_back(u);
}

void dfs(int u) {
  vis[u] = true;
  cur.push_back(u);
  for (const auto &v : gg[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  #ifndef LOCAL
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
  #endif

  int n, m;
  std::cin >> n >> m;

  while (m--) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    gg[v].push_back(u);
  }

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

  std::reverse(order.begin(), order.end());

  for (int i = 1; i <= n; i++) {
    vis[i] = false;
  }

  std::vector<std::vector<int>> comp;

  for (const auto &u : order) {
    if (!vis[u]) {
      cur.clear();
      dfs(u);
      comp.push_back(cur);
    }
  }

  std::cout << (int) comp.size() << '\n';
  for (auto &w : comp) {
    std::sort(w.begin(), w.end());
    for (const auto &v : w) {
      std::cout << v << ' ';
    }
    std::cout << '\n';
  }

  return 0;
}