Pagini recente » Cod sursa (job #1607364) | Cod sursa (job #540085) | Cod sursa (job #663073) | Cod sursa (job #1081692) | Cod sursa (job #3148989)
#include <vector>
#include <fstream>
#include <stack>
#include <unordered_set>
#define MAX_SIZE 100001
std::vector<int> time_of_entry(MAX_SIZE, 0);
std::vector<bool> visited(MAX_SIZE, false);
std::vector<int> low(MAX_SIZE, 0);
std::stack<std::pair<int, int>> stack;
std::vector<std::unordered_set<int>> components;
int timer = 0;
struct Graph {
private:
std::vector<std::vector<int>> vec;
public:
explicit Graph(int nodes) {
vec.resize(nodes + 1);
}
void add_edge(int to, int from) {
vec[to].push_back(from);
vec[from].push_back(to);
}
const std::vector<int> &operator[](int node) {
return vec[node];
}
};
Graph graph(MAX_SIZE);
void dfs(int node, int root = 0) {
time_of_entry[node] = low[node] = timer++;
visited[node] = true;
int children = 0;
for (const auto &x: graph[node]) {
if (x == root) continue;
if (visited[x]) {
low[node] = std::min(low[node], time_of_entry[x]);
} else {
stack.emplace(x, node);
dfs(x, node);
low[node] = std::min(low[node], low[x]);
if (low[x] >= time_of_entry[node]) {
components.emplace_back();
while (!stack.empty()) {
auto top = stack.top();
stack.pop();
components.back().insert(top.first);
components.back().insert(top.second);
if (top.first == x && top.second == node) break;
}
}
children++;
}
}
}
int main() {
std::ifstream input("biconex.in");
std::ofstream output("biconex.out");
int n, m;
input >> n >> m;
while (m--) {
int x, y;
input >> x >> y;
graph.add_edge(x, y);
}
for (int i = 1; i <= n; ++i) {
if (!visited[i]) dfs(i);
}
output << components.size() << '\n';
for (const auto &component: components) {
for (const auto &node: component) {
output << node << " ";
}
output << '\n';
}
return 0;
}