Pagini recente » Cod sursa (job #2796180) | Monitorul de evaluare | Cod sursa (job #3331310) | Cod sursa (job #3335288) | Cod sursa (job #3330691)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
// Pasul 1: DFS normal pentru a obtine ordinea terminarii nodurilor
void dfs1(int nod, const vector<vector<int>>& graf, vector<bool>& viz, vector<int>& stiva) {
viz[nod]=true;
for(auto vecin:graf[nod]){
if(!viz[vecin]){
dfs1(vecin,graf,viz,stiva);
}
}
stiva.push_back(nod);
}
// Pasul 2: DFS pe graful INVERSAT pentru a extrage o componenta
void dfs2(int nod, const vector<vector<int>>& graf_inv, vector<bool>& viz, vector<int>& componenta_curenta) {
viz[nod]=false;
componenta_curenta.push_back(nod);
for(auto vecin:graf_inv[nod]){
if(viz[vecin]){
dfs2(vecin,graf_inv,viz,componenta_curenta);
}
}
}
int main() {
int n,m,x,y;
in>>n>>m;
vector<vector<int>> graf(n + 1);
vector<vector<int>> graf_inv(n + 1);
for (int i = 1; i <= m; i++) {
in >> x >> y;
graf[x].push_back(y);
graf_inv[y].push_back(x); // AICI e secretul: inversam muchiile!
}
vector<bool> viz(n + 1, false);
vector<int> stiva;
// Pasul 1: Umplem stiva
for (int i = 1; i <= n; i++) {
if (!viz[i])
dfs1(i, graf, viz, stiva);
}
// Pasul 2: Procesam nodurile din stiva in ordine INVERSA (de la ultimul la primul)
vector<vector<int>>toate_ctc;
for(int i=stiva.size()-1;i>=0;i--){
int nod=stiva[i];
if(viz[nod]){
vector<int>componenta;
dfs2(nod,graf_inv,viz,componenta);
toate_ctc.push_back(componenta);
}
}
// Afisare
out<<toate_ctc.size()<<"\n";
for(auto ctc:toate_ctc){
for(int nod:ctc){
out<<nod<<" ";
}
out<<"\n";
}
return 0;
}