Cod sursa(job #3341276)

Utilizator domdiridomdidomDominik domdiridomdidom Data 18 februarie 2026 20:09:16
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <algorithm>
#include <fstream>
#include <stack>
#include <vector>

using std::vector, std::stack;

std::ifstream in("ctc.in");
std::ofstream out("ctc.out");

void tarjan(vector<vector<int>> & megoldas, vector<vector<int>> & graf, stack<int> & s, vector<int> & index, vector<int> & lowlink, vector<bool> & onStack, int n, int v, int & idx) {
   index[v] = idx;
   lowlink[v] = idx;
   idx++;
   onStack[v] = true;
   s.push(v);
   for(const auto & w : graf[v]) {
      if(index[w] == -1) {
         tarjan(megoldas, graf, s, index, lowlink, onStack, n, w, idx);
         lowlink[v] = std::min(lowlink[v], lowlink[w]);
      }
      else if(onStack[w]) {
         lowlink[v] = std::min(lowlink[v], index[w]);
      }
   }
   if(lowlink[v] == index[v]) {
      int w;
      megoldas.push_back(vector<int>());
      do {
         w = s.top();
         s.pop();
         onStack[w] = false;
         megoldas[megoldas.size() - 1].push_back(w + 1);
      } while(v != w);
   }
}

int main() {
   int n, m;
   in >> n >> m;
   vector<vector<int>> graf(n), megoldas;
   vector<bool> onStack(n, 0);
   vector<int> index(n, -1), lowlink(n, -1);
   while(m--) {
      int u, v;
      in >> u >> v;
      graf[--u].push_back(--v);
   }
   int idx = 0;
   for(int i = 0; i < n; i++) {
      if(index[i] == -1) {
         stack<int> s;
         tarjan(megoldas, graf, s, index, lowlink, onStack, n, i, idx);
      }
   }
   for(int i = megoldas.size() - 1; i >= 0; i--) {
      std::sort(megoldas[i].begin(), megoldas[i].begin() + megoldas[i].size());
      for(const auto & e : megoldas[i])
         out << e << ' ';
      out << '\n';
   }
}