Cod sursa(job #3371889)

Utilizator nstefanNeagu Stefan nstefan Data 1 noiembrie 2026 15:59:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

#include <cstdio>
#include <deque>
#include <vector>
using namespace std;

#ifdef INFOARENA
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cin fin
#define cout fout
#endif

// Assumes vertices are values between 1 and `n` (inclusive).
// Assumes g and gt are of size `n + 1`.
// n  - number of nodes
// g  - adjacency list
// gt - adjacency list of the transposed graph
vector<vector<int>> kosaraju_ctc(const int n, const vector<vector<int>>& g, const vector<vector<int>>& gt) {
  vector<vector<int>> ans;
  vector<int> order;
  vector<int> visited(n + 1, 0);

  auto dfs = [&](auto& self, const vector<vector<int>>& g, int node, vector<int>& out) {
    if (visited[node]) return;
    visited[node] = 1;

    for (auto neigh : g[node])
      if (!visited[neigh])
        self(self, g, neigh, out);

    out.push_back(node);
  };

  // Step 1: topological sort (ok, reversed topological sort)
  for (int i = 1; i <= n; i++)
    if (!visited[i])
      dfs(dfs, g, i, order);

  // Step 2: finding ctc
  fill(visited.begin(), visited.end(), 0);
  for (int i = order.size() - 1; i >= 0; i--) 
    if (!visited[order[i]]) {
      ans.emplace_back();
      dfs(dfs, gt, order[i], ans.back());
    }

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n + 1);
  vector<vector<int>> adjTranspus(n + 1);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adjTranspus[b].push_back(a);
  }

#ifndef INFOARENA
  for (auto& v : adj)
    sort(v.begin(), v.end());
  for (auto& v : adjTranspus)
    sort(v.begin(), v.end());
#endif

  ////////

  auto ans = kosaraju_ctc(n, adj, adjTranspus);

  ////////

  cout << ans.size() << '\n';
  for (auto comp : ans) {
    for (auto node : comp) {
      cout << node << ' ';
    }
    cout << '\n';
  }
}