Pagini recente » Cod sursa (job #1083846) | Cod sursa (job #1378979) | Cod sursa (job #3040731) | Cod sursa (job #1752869) | Cod sursa (job #2869827)
#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>
#include <stack>
using u32 = uint32_t;
using i32 = int32_t;
constexpr size_t MAX_NODES = 100000;
std::array<std::vector<size_t>, MAX_NODES> edges;
std::array<size_t, MAX_NODES> level;
std::array<size_t, MAX_NODES> low;
std::vector<std::vector<size_t>> result;
std::array<bool, MAX_NODES> viz;
std::stack<size_t> order;
void dfs (size_t node, size_t parent) {
viz[node] = true;
low[node] = level[node];
order.emplace(node);
for (auto to: edges[node]) {
if (to == parent)
continue;
if (viz[to]) {
low[node] = std::min(low[node], level[to]);
continue;
}
level[to] = level[node] + 1;
dfs(to, node);
low[node] = std::min(low[node], low[to]);
if (level[node] <= low[to]) {
/* critical edge */
}
if (level[node] == low[node]) {
/* articulation point */
}
if (level[node] == low[node] || level[node] <= low[to]) {
result.emplace_back();
size_t last;
do {
last = order.top();
order.pop();
result.back().emplace_back(last);
} while (last != to);
result.back().emplace_back(node);
}
}
}
int main () {
std::ifstream in("biconex.in");
std::ofstream out("biconex.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;
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
dfs(0, -1);
out << result.size() << '\n';
for (const auto &component: result) {
for (const auto &node: component)
out << node + 1 << ' ';
out << '\n';
}
}