Pagini recente » Cod sursa (job #1837352) | Cod sursa (job #1963887) | Cod sursa (job #1749106) | Istoria paginii utilizator/gabipintea | Cod sursa (job #3268946)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int nodes, edges, numCtc;
vector <int> graph[100001], trans[100001];
vector <int> stiva;
vector <int> ctc[100001];
bool viz[100001];
void dfsGraph (int x){
if (viz[x])
return;
viz[x] = true;
for (auto idx:graph[x]){
dfsGraph(idx);
}
stiva.push_back(x);
}
void dfsTrans (int x){
if (viz[x])
return;
viz[x] = true;
ctc[numCtc].push_back(x);
for (auto idx:trans[x]){
dfsTrans(idx);
}
}
int main (){
int x, y;
in >> nodes >> edges;
for (int i=1; i<=edges; ++i){
in >> x >> y;
graph[x].push_back(y);
trans[y].push_back(x);
}
for (int i=1; i<=nodes; ++i){
if (viz[i] == false)
dfsGraph(i);
}
for (int i=1; i<=nodes; ++i)
viz[i] = false;
for (int i=stiva.size()-1; i>=0; --i){
if (viz[stiva[i]] == false){
dfsTrans(stiva[i]);
numCtc++;
}
}
out << numCtc << '\n';
for (int i=0; i<numCtc; ++i){
for (auto idx:ctc[i])
out << idx << ' ';
out << '\n';
}
return 0;
}