Pagini recente » Cod sursa (job #1481352) | Cod sursa (job #2804895) | Cod sursa (job #13435) | Cod sursa (job #863050) | Cod sursa (job #3030684)
#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 array<bool, 100'010> in_stack;
static int memory = 0;
low[node] = level[node] = memory ++;
comp.emplace(node);
in_stack[node] = true;
for (auto to: edges[node]) {
if (level[to] == -1)
dfs(to);
if (in_stack[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();
in_stack[last] = false;
} 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';
}
}