Pagini recente » Cod sursa (job #1867928) | Cod sursa (job #720603) | Cod sursa (job #2168727) | Cod sursa (job #1189426) | Cod sursa (job #2667091)
#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;
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 : muchie_din[i]) {
if (vizitat[j] == 0) {
parcurgere(j);
minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[j]);
}
else if (e_in_stiva[j] == 1)
minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[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);
} while (nod!=i);
componente.push_back(auxiliar);
}
}
void afisare() {
g<<componente.size()<<endl;
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();
}