Cod sursa(job #3371376)

Utilizator nstefanNeagu Stefan nstefan Data 29 octombrie 2026 23:10:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

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

vector<int> adj[100'010];
vector<int> adjTranspus[100'010];

void kosaraju1(int node, vector<int>& visited, std::deque<int>& dq) {
  if (visited[node])
    return;

  visited[node] = 1;
  for (auto neigh : adj[node]) {
    if (visited[neigh])
      continue;
    kosaraju1(neigh, visited, dq);
  }

  dq.push_front(node);
}

void kosaraju2(int node, int compRoot, vector<int>& ctc) {
  if (ctc[node] != 0)
    return;

  ctc[node] = compRoot;
  for (auto neigh : adjTranspus[node]) {
    if (ctc[neigh])
      continue;
    kosaraju2(neigh, compRoot, ctc);
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  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

  ////////

  vector<int> visited(n + 10);
  vector<int> ctc(n + 10);

  std::deque<int> dq;
  for (int node = 1; node <= n; node++) {
    if (visited[node])
      continue;

    kosaraju1(node, visited, dq);
  }

  for (auto node2 : dq) {
    if (ctc[node2])
      continue;

    kosaraju2(node2, node2, ctc);
  }

  ////////

  map<int, vector<int>> ans;
  for (int node = 1; node <= n; node++) {
    ans[ctc[node]].push_back(node);
  }

  cout << ans.size() << '\n';
  for (auto [_, v] : ans) {
    for (auto node : v) {
      cout << node << ' ';
    }
    cout << '\n';
  }
}