Pagini recente » Cod sursa (job #2530038) | Cod sursa (job #1322047) | Cod sursa (job #474411) | Cod sursa (job #3284693) | Cod sursa (job #2817168)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define NMax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> S;
vector<int> GT[NMax], CTC[NMax];
struct muchie {
int destinatie, cost, capacitate;
muchie(int destinatie, int cost, int capacitate) : destinatie(destinatie), cost(cost), capacitate(capacitate) {}
};
vector<vector<muchie>> G;
int N, M, NrCTC;
int beenThere[NMax];
void Read() {
fin >> N >> M;
G.resize(N + 1, vector<muchie>());
for (int i = 1; i <= M; i++) {
int x, y, cost = 0, capacitate = 0;
fin >> x >> y;
G[x].push_back(muchie(y, cost, capacitate)); // Construim graful G
GT[y].push_back(x); // Construim transpusa grafului G
}
}
void DFSP(int Nod) {
beenThere[Nod] = 1;
for (auto &i: G[Nod]) {
int Vecin = i.destinatie;
if (!beenThere[Vecin])
DFSP(Vecin);
}
S.push(Nod);
}
void DFSM(int Nod) {
beenThere[Nod] = 2;
CTC[NrCTC].push_back(Nod);
for (unsigned int i = 0; i < GT[Nod].size(); i++) {
int Vecin = GT[Nod][i];
if (beenThere[Vecin] == 1)
DFSM(Vecin);
}
}
void Solve() {
for (int i = 1; i <= N; i++)
if (!beenThere[i])
DFSP(i);
while (!S.empty()) {
int Nod = S.top();
cout << Nod << " ";
if (beenThere[Nod] == 1) {
NrCTC++;
DFSM(Nod);
}
S.pop();
}
// while(!S.empty()) {
// fout << S.top() << " ";
// S.pop();
// }
}
void Print() {
fout << NrCTC << "\n";
for (int i = 1; i <= NrCTC; i++) {
for (unsigned int j = 0; j < CTC[i].size(); j++)
fout << CTC[i][j] << " ";
fout << "\n";
}
}
int main() {
Read();
Solve();
Print();
return 0;
}