Pagini recente » Cod sursa (job #2257617) | Cod sursa (job #285048) | Cod sursa (job #1675829) | Cod sursa (job #2752709) | Cod sursa (job #2869703)
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>
constexpr size_t MAX_NODES = 100000;
namespace normal {
std::array<std::vector<size_t>, MAX_NODES> edges;
std::array<bool, MAX_NODES> viz;
void dfs (size_t node, std::vector<size_t> &appender) {
viz[node] = true;
for (auto to: edges[node])
if (!viz[to])
dfs(to, appender);
appender.emplace_back(node);
}
}
namespace transposed {
std::array<std::vector<size_t>, MAX_NODES> edges;
std::array<bool, MAX_NODES> viz;
void dfs (size_t node, std::vector<size_t> &appender) {
viz[node] = true;
for (auto to: edges[node])
if (!viz[to])
dfs(to, appender);
appender.emplace_back(node);
}
}
int main () {
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
size_t nodeCount, edgeCount;
in >> nodeCount >> edgeCount;
for (size_t i = 0; i != edgeCount; ++ i) {
size_t x, y;
in >> x >> y;
-- x, -- y;
normal::edges[x].emplace_back(y);
transposed::edges[y].emplace_back(x);
}
std::vector<size_t> order;
for (size_t i = 0; i != nodeCount; ++ i)
if (!normal::viz[i])
normal::dfs(i, order);
std::vector<std::vector<size_t>> strongComponents;
for (auto it = order.crbegin(); it != order.crend(); ++ it)
if (!transposed::viz[*it]) {
strongComponents.emplace_back();
transposed::dfs(*it, strongComponents.back());
}
out << strongComponents.size() << '\n';
for (const auto &component: strongComponents) {
for (const auto &node: component)
out << node + 1 << ' ';
out << '\n';
}
}