Pagini recente » Cod sursa (job #1510867) | Cod sursa (job #35431) | Cod sursa (job #2746144) | Cod sursa (job #723210) | Cod sursa (job #2863497)
#include <array>
#include <fstream>
#include <iterator>
#include <vector>
using uint = unsigned int;
using inserter_t = std::back_insert_iterator<std::vector<uint>>;
constexpr uint MAX_NODES = 100000;
std::array<std::vector<uint>, MAX_NODES> edges;
std::array<std::vector<uint>, MAX_NODES> segde;
void dfs1 (uint node, std::vector<bool>& viz, inserter_t inserter) {
viz[node] = true;
for (auto to: edges[node])
if (!viz[to])
dfs1(to, viz, inserter);
inserter = node;
}
void dfs2 (uint node, std::vector<bool>& viz, inserter_t inserter) {
viz[node] = true;
for (auto to: segde[node])
if (!viz[to])
dfs2(to, viz, inserter);
inserter = node + 1;
}
int main () {
std::ifstream f("ctc.in");
f.exceptions(f.badbit | f.failbit | f.eofbit);
std::ofstream g("ctc.out");
uint n, m;
f >> n >> m;
for (uint i = 0; i != m; ++ i) {
uint x, y;
f >> x >> y;
-- x, -- y;
edges[x].emplace_back(y);
segde[y].emplace_back(x);
}
std::vector<uint> order;
{
std::vector<bool> viz(n);
auto inserter = std::back_inserter(order);
for (uint i = 0; i != n; ++ i)
if (!viz[i])
dfs1(i, viz, inserter);
}
std::vector<std::vector<uint>> ans;
{
std::vector<bool> viz(n);
for (auto it = order.crbegin(); it != order.crend(); ++ it)
if (!viz[*it]) {
ans.emplace_back();
dfs2(*it, viz, std::back_inserter(ans.back()));
}
}
g << ans.size() << '\n';
for (const auto &vec: ans) {
std::copy(vec.begin(), vec.end(), std::ostream_iterator<uint>(g, " "));
g << '\n';
}
}