Pagini recente » Cod sursa (job #2816902) | Cod sursa (job #2669950) | Cod sursa (job #3231915) | Cod sursa (job #494322) | Cod sursa (job #2817046)
#include <iostream>
#include <fstream>
#include <vector>
#define d(a) std::cout << a << std::endl;
const int INF = 1e9 + 7;
const int NMAX = 1e5;
int n, m;
std::vector<int> graph[1 + NMAX];
std::vector<std::pair<int, int>> stack;
int height[1 + NMAX];
std::vector<std::vector<int>> ans;
int dfs(int node, int h) {
//std::printf("called for node = %d\n", node);
height[node] = h;
int minHeight = INF;
for (int child : graph[node]) {
if (height[child] != 0)
minHeight = std::min(minHeight, height[child]);
else {
//std::printf("node %d -> child %d\n", node, child);
stack.emplace_back(node, child);
int childMinHeight = dfs(child, 1 + h);
if (childMinHeight >= h) {
//std::printf("found component @ node = %d, child = %d w/ height = %d\n", node, child, childMinHeight);
ans.emplace_back();
while (stack.back().first != node && stack.back().second != child) {
ans.back().push_back(stack.back().second);
stack.pop_back();
}
ans.back().push_back(child);
ans.back().push_back(node);
stack.pop_back();
}
minHeight = std::min(minHeight, childMinHeight);
}
}
return minHeight;
}
int main() {
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
in >> n >> m;
while (m--) {
int a, b;
in >> a >> b;
// std::cout << a << " -- " << b << "\n";
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 1);
out << ans.size() << '\n';
for (auto &comp : ans) {
for (int i : comp)
out << i << ' ';
out << '\n';
}
return 0;
}