Pagini recente » Cod sursa (job #428472) | Cod sursa (job #1196407) | Cod sursa (job #3235995) | Cod sursa (job #143626) | Cod sursa (job #1165125)
#include <fstream>
#include <vector>
using namespace std;
const int MAX = 101101;
int N, M;
bool Viz[MAX], ctc[MAX];
vector<int> discovered, V;
vector<int> GIn[MAX], GOut[MAX];
vector< vector<int> > CTC;
void citire() {
ifstream in("ctc.in");
in >> N >> M;
for(int i = 1, A, B; i <= M; i++) {
in >> A >> B;
GIn[B].push_back(A);
GOut[A].push_back(B);
} in.close();
}
void DFF(int nod) {
Viz[nod] = true;
for(size_t i = 0; i < GOut[nod].size(); i++) {
int dest = GOut[nod][i];
if(!Viz[dest])
DFF(dest);
} discovered.push_back(nod);
}
void DFB(int nod) {
ctc[nod] = true;
V.push_back(nod);
for(size_t i = 0; i < GIn[nod].size(); i++) {
int dest = GIn[nod][i];
if(!ctc[dest])
DFB(dest);
}
}
void solve() {
for(int i = 1; i <= N; i++) {
if(!Viz[i]) {
DFF(i);
}
}
for(; discovered.size(); discovered.pop_back()) {
int nod = discovered.back();
if(!ctc[nod]) {
V.clear();
DFB(nod);
CTC.push_back(V);
}
}
}
void afisare() {
ofstream out("ctc.out");
out << CTC.size() << "\n";
for(size_t i = 0; i < CTC.size(); i++) {
for(size_t j = 0; j < CTC[i].size(); j++) {
out << CTC[i][j] << " ";
} out << "\n";
} out.close();
}
int main() {
citire();
solve();
afisare();
}