Cod sursa(job #3300715)

Utilizator vlvdVlad Hosu vlvd Data 18 iunie 2025 17:38:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

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

int n, m;
vector<vector<int>> g, gt;
stack<int> nodes;
vector<int> viz;

void dfs(int node) {
  viz[node] = 1;
  for (int neigh : g[node]) {
    if (!viz[neigh]) {
      dfs(neigh);
    }
  }
  nodes.push(node);
}

void create_gt() {
  gt.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    for (int y : g[i]) {
      gt[y].push_back(i);
    }
  }
}

void ctc_dfs(int node, int count) {
  viz[node] = count;
  for (int neigh : gt[node]) {
    if (!viz[neigh]) {
      ctc_dfs(neigh, count);
    }
  }
}

int main() {
  fin >> n >> m;
  g.resize(n + 1);
  viz.resize(n + 1, 0);

  for (int i = 0; i < m; i++) {
    int x, y;
    fin >> x >> y;
    g[x].push_back(y);
  }

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

  fill(viz.begin(), viz.end(), 0);
  create_gt();

  int count = 1;
  while (!nodes.empty()) {
    int start = nodes.top();
    nodes.pop();
    if (!viz[start]) {
      ctc_dfs(start, count);
      count++;
    }
  }

  vector<vector<int>> components(count);
  for (int i = 1; i <= n; i++) {
    components[viz[i]].push_back(i);
  }

  fout << count - 1 << '\n';
  for (int i = 1; i < count; i++) {
    for (int node : components[i]) {
      fout << node << " ";
    }
    fout << '\n';
  }

  return 0;
}