Pagini recente » Cod sursa (job #3139392) | Cod sursa (job #2433349) | Cod sursa (job #53570) | Cod sursa (job #1334644) | Cod sursa (job #3030691)
#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;
static int memory = 0;
low[node] = level[node] = memory ++;
comp.emplace(node);
for (auto to: edges[node]) {
if (level[to] == -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);
for (int i = 1; i <= n; ++ i)
if (level[i] == -1)
dfs(i);
out << result.size() << '\n';
for (const auto &comp: result) {
for (const auto &node: comp)
out << node << ' ';
out << '\n';
}
}