Pagini recente » Cod sursa (job #3248811) | Borderou de evaluare (job #2247448) | Cod sursa (job #748630) | Cod sursa (job #2598758) | Cod sursa (job #1377561)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int kNMax = 200010;
int n, index[kNMax], viz[kNMax], link[kNMax], nr = 1;
int nr_sol;
vector <int> G[kNMax], Stack, sol[kNMax];
void Citire() {
ifstream in("ctc.in");
int x, y, m;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
in >> x >> y;
G[x].push_back(y);
}
in.close();
}
void Dfs(int nod) {
int vecin, i;
viz[nod] = 1;
index[nod] = nr;
link[nod] = nr;
++nr;
Stack.push_back(nod);
for (int i = 0; i < G[nod].size(); ++i){
vecin = G[nod][i];
if (!index[vecin]) {
Dfs(vecin);
if (link[nod] > link[vecin])
link[nod] = link[vecin];
} else if (viz[vecin])
if (link[nod] > link[vecin])
link[nod] = link[vecin];
}
if (link[nod] == index[nod]) {
sol[++nr_sol].push_back(Stack.back());
viz[Stack.back()] = 0;
while (Stack.back() != nod) {
Stack.pop_back();
sol[nr_sol].push_back(Stack.back());
viz[Stack.back()] = 0;
}
Stack.pop_back();
}
}
void Solve() {
for (int i = 1; i <= n; ++i)
if(!index[i])
Dfs(i);
}
void Afisare() {
ofstream out("ctc.out");
out << nr_sol << '\n';
for (int i = nr_sol; i >= 1; --i) {
for (int j = sol[i].size() - 1; j >= 0; --j)
out << sol[i][j] << ' ';
out << '\n';
}
out.close();
}
int main() {
Citire();
Solve();
Afisare();
return 0;
}