Pagini recente » Cod sursa (job #2709019) | Cod sursa (job #2894045) | Cod sursa (job #2527428) | Cod sursa (job #1189440) | Cod sursa (job #2667112)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int vizitat[100001], minim_pe_ciclul_lui[100001];
bool e_in_stiva[100001];
vector<int> muchie_din[100001];//, auxiliar;
//vector<vector<int>> componente;
stack<int> componenta_curenta;
int n, m, curent = 1, nr=0;
string rezultat = "";
void citire() {
f>>n>>m;
for(int i=0; i<m; i++) {
int a, b;
f>>a>>b;
muchie_din[a].push_back(b);
}
f.close();
}
void parcurgere(int i) {
vizitat[i] = minim_pe_ciclul_lui[i] = curent++;
componenta_curenta.push(i);
e_in_stiva[i] = 1;
for(int j=0; j<muchie_din[i].size(); j++) {
if (vizitat[muchie_din[i][j]] == 0) {
//cout<<"A"<<endl;
parcurgere(muchie_din[i][j]);
minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[muchie_din[i][j]]);
}
else if (e_in_stiva[muchie_din[i][j]] == 1)
minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[muchie_din[i][j]]);
}
if (minim_pe_ciclul_lui[i] == vizitat[i]) {
int nod;
//auxiliar.clear();
do {
nod = componenta_curenta.top();
componenta_curenta.pop();
e_in_stiva[nod] = 0;
//auxiliar.push_back(nod);
rezultat = rezultat + to_string(nod) + " ";
} while (nod!=i);
nr++;
//componente.push_back(auxiliar);
rezultat = rezultat + "\n";
}
}
void afisare() {
//g<<componente.size()<<endl;
g<<nr<<'\n';
g<<rezultat;
// for(int i=0; i<componente.size(); i++) {
// for(int j : componente[i])
// g<<j<<' ';
// g<<endl;
// }
g.close();
}
int main() {
citire();
for(int i=1; i<=n; i++)
if (vizitat[i] == 0)
parcurgere(i);
afisare();
}