Pagini recente » Cod sursa (job #2207229) | Cod sursa (job #1357769) | Cod sursa (job #2095904) | Cod sursa (job #2313281) | Cod sursa (job #3347757)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
int n, m, timp;
bool inst[NMAX];
int nma[NMAX], d[NMAX];
stack<int> s;
vector<int> G[NMAX];
vector<vector<int>> CTC;
void citire() {
fin >> n >> m;
for(int i = 1, x, y; i <= m; ++i) {
fin >> x >> y;
G[x].push_back(y);
}
}
void dfs(int x) {
d[x] = ++timp;
nma[x] = timp;
inst[x] = 1;
s.push(x);
for(const auto& y : G[x]) {
if(d[y] == 0) {
dfs(y);
nma[x] = min(nma[x], nma[y]);
} else if(inst[y]) {
nma[x] = min(nma[x], d[y]);
}
}
if(nma[x] != d[x]) return;
CTC.push_back(vector<int>());
int y;
do {
y = s.top();
s.pop();
CTC.back().push_back(y);
inst[y] = 0;
} while(y != x);
}
void afis() {
fout << CTC.size() << '\n';
for(const auto& v : CTC) {
for(const auto& x : v) {
fout << x << ' ';
}
fout << '\n';
}
}
int main() {
citire();
dfs(1);
afis();
return 0;
}