Pagini recente » Cod sursa (job #1189546) | Cod sursa (job #1616372) | Cod sursa (job #431453) | Cod sursa (job #3149976) | Cod sursa (job #2817177)
#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;
struct muchie {
int destinatie, cost, capacitate;
muchie(int destinatie, int cost, int capacitate) : destinatie(destinatie), cost(cost), capacitate(capacitate) {}
};
vector<vector<muchie>> G, GT;
vector<vector<int>> CTC;
int N, M, NrCTC;
int beenThere[NMax];
void Read() {
fin >> N >> M;
G.resize(N + 1, vector<muchie>());
GT.resize(N + 1, vector<muchie>());
CTC.resize(N + 1, vector<int>());
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(muchie(x, cost, capacitate)); // Construim transpusa grafului G
}
for (int i = 1; i <= N; i++) {
for (auto &j: G[i])
GT[j.destinatie].push_back(muchie(i, j.cost, j.capacitate));
}
}
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 (auto &i: GT[Nod]) {
int Vecin = i.destinatie;
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();
}
}
void Print() {
fout << NrCTC << "\n";
for (int i = 1; i <= NrCTC; i++) {
for (auto &j: CTC[i])
fout << j << " ";
fout << "\n";
}
}
int main() {
Read();
Solve();
Print();
return 0;
}