Cod sursa(job #3370787)

Utilizator RaducuSebasRaducu Sebastian RaducuSebas Data 27 octombrie 2026 11:45:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[100001];
vector<int> adjT[100001];
bool viz[100001];
vector<int> ord;

vector<vector<int>> ctc;
vector<int> comp;

void dfs1(int nod) {
  viz[nod] = true;
  for (int vecin : adj[nod])
    if (!viz[vecin])
      dfs1(vecin);
  ord.push_back(nod);
}

void dfs2(int nod) {
  viz[nod] = false;
  comp.push_back(nod);
  for (int vecin : adjT[nod]) {
    if (viz[vecin]) {
      dfs2(vecin);
    }
  }
}

int main() {
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");

  int n, m;
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adjT[v].push_back(u);
  }

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

  for (int i = n - 1; i >= 0; i--) {
    int nod = ord[i];
    if (viz[nod]) {
      comp.clear();
      dfs2(nod);
      ctc.push_back(comp);
    }
  }

  cout << ctc.size() << '\n';
  for (const auto &comp : ctc)
    for (int i = 0; i < (int)comp.size(); i++) {
      cout << comp[i];
      if (i + 1 == (int)comp.size())
        cout << '\n';
      else
        cout << " ";
    }
  cin.close();
  cout.close();

  return 0;
}