Pagini recente » Cod sursa (job #831397) | Cod sursa (job #598744) | Cod sursa (job #2340266) | Cod sursa (job #922553) | Cod sursa (job #3030673)
#include <bits/stdc++.h>
using namespace std;
array<int, 100'010> level, low;
array<vector<int>, 100'010> edges;
vector<vector<int>> result;
void dfs(int node) {
static stack<int> comp;
low[node] = level[node];
comp.emplace(node);
for (auto to: edges[node]) {
if (level[to] != -1) {
low[node] = min(low[node], low[to]);
continue;
}
level[to] = level[node] + 1;
dfs(to);
low[node] = min(low[node], low[to]);
}
if (level[node] == low[node]) {
result.emplace_back();
int last;
do {
result.back().emplace_back(last = comp.top());
comp.pop();
} while (last != node);
}
}
int main () {
ifstream in("ctc.in");
in.exceptions(in.failbit);
ofstream out("ctc.out");
out.exceptions(out.failbit);
int n, m;
in >> n >> m;
for (int i = 0; i < m; ++ i) {
int x, y;
in >> x >> y;
edges[x].emplace_back(y);
}
std::fill_n(level.begin() + 1, n, -1);
level[1] = 0;
dfs(1);
out << result.size() << '\n';
for (const auto &comp: result) {
for (const auto &node: comp)
out << node << ' ';
out << '\n';
}
}