Pagini recente » Cod sursa (job #1612844) | Cod sursa (job #1630670) | Cod sursa (job #1483892) | Cod sursa (job #1515848) | Cod sursa (job #2666947)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int vizitat[100001], minim_pe_ciclul_lui[100001];
vector<int> muchie_din[100001], componente[100001];
stack<int> componenta_curenta;
set<int> e_in_stiva;
int n, m, curent = 1, nr=0;
void citire() {
f>>n>>m;
for(int i=0; i<m; i++) {
int a, b;
f>>a>>b;
muchie_din[a].push_back(b);
}
}
void parcurgere(int i) {
vizitat[i] = curent;
minim_pe_ciclul_lui[i] = curent;
componenta_curenta.push(i);
e_in_stiva.insert(i);
curent++;
for(int j=0; j<muchie_din[i].size(); j++) {
//cout<<muchie_din[i][j]<<' ';
if (vizitat[muchie_din[i][j]] == 0) {
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.find(muchie_din[i][j]) != e_in_stiva.end())
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]) {
//cout<<" terminat componenta"<<endl;
int nod;
do {
nod = componenta_curenta.top();
componenta_curenta.pop();
e_in_stiva.erase(nod);
componente[nr].push_back(nod);
} while (i!=nod);
}
}
void afisare() {
g<<nr+1<<endl;
for(int i=0; i<nr; i++) {
for(int j=0; j<componente[i].size(); j++)
g<<componente[i][j]<<' ';
g<<endl;
}
}
int main() {
citire();
f.close();
for(int i=1; i<=n; i++)
if (vizitat[i] == 0)
parcurgere(i);
afisare();
g.close();
}