Cod sursa(job #3370744)

Utilizator RaducuSebasRaducu Sebastian RaducuSebas Data 27 octombrie 2026 10:44:47
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[1000];
vector<int> adjT[1000];
bool viz[1000];
vector<int> ordine;

vector<vector<int>> ctc;
vector<int> componenta_curenta;

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

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

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

  int n, m;
  fin >> n >> m;

  for (int i = 0; i < m; i++) {
    int u, v;
    fin >> 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 = ordine[i];
    if (viz[nod]) {
      componenta_curenta.clear();
      dfs2(nod);
      ctc.push_back(componenta_curenta);
    }
  }

  fout << ctc.size() << '\n';
  for (auto &comp : ctc) {
    for (int i = 0; i < (int)comp.size(); i++) {
      fout << comp[i] << (i + 1 == (int)comp.size() ? '\n' : ' ');
    }
  }

  fin.close();
  fout.close();

  return 0;
}