Cod sursa(job #2925473)

Utilizator BluThund3rRadu George BluThund3r Data 15 octombrie 2022 12:50:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

stack<int> s;
vector<vector<int>> adj, adjt, components;
vector<bool> viz;
vector<int> currComponent;

void dfs(int node) {
   viz[node] = true;
   for(auto nextNode : adj[node])
       if(!viz[nextNode])
           dfs(nextNode);

   s.push(node);
}

void showComponent(int node) {
   viz[node] = false;
   currComponent.push_back(node);
   for(auto nextNode : adjt[node])
       if(viz[nextNode])
           showComponent(nextNode);
}

int main() {

   int n, m, x, y;
   in >> n >> m;
   adj.resize(n + 1);
   adjt.resize(n + 1);
   viz.resize(n + 1, false);
   while(m --) {
       in >> x >> y;
       adj[x].push_back(y);
       adjt[y].push_back(x);
   }

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

   // pentru a nu mai seta toate elementele lui viz la false, de acum inainte o sa folosesc pe dos acest vector
   // i.e. daca un nod este vizitat in timpul lui showComponent(), el va fi marcat cu false in viz

   while(!s.empty()) {
       if(viz[s.top()]) {
           showComponent(s.top());
           s.pop();
           components.push_back(currComponent);
           currComponent.clear();
       }
       else
           s.pop();
   }

   out << components.size() << '\n';
   for(auto comp : components){
       for(auto node : comp)
           out << node << ' ';
       out << '\n';
   }

   return 0;
}