Pagini recente » Cod sursa (job #3353905) | Cod sursa (job #3317478) | Cod sursa (job #3336142) | Monitorul de evaluare | Cod sursa (job #3357789)
#include <vector>
#include <fstream>
#include <stack>
#include <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<int> stack;
std::vector<std::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 parent) {
time_of_entry[node] = low[node] = timer++;
visited[node] = true;
stack.push(node);
for (const auto &neighbor : graph[node]) {
if (neighbor == parent) continue;
if (visited[neighbor]) {
low[node] = std::min(low[node], time_of_entry[neighbor]);
} else {
dfs(neighbor, node);
low[node] = std::min(low[node], low[neighbor]);
}
}
if (low[node] == time_of_entry[node]) {
std::set<int> component;
while (!stack.empty()) {
int current = stack.top();
stack.pop();
component.insert(current);
if (current == node) break;
}
components.push_back(component);
}
}
int main() {
std::ifstream input("biconex.in");
std::ofstream output("biconex.out");
int n, m;
input >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
input >> x >> y;
graph.add_edge(x, y);
}
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, -1);
}
}
output << components.size() << '\n';
for (const auto &component : components) {
for (const auto &node : component) {
output << node << " ";
}
output << '\n';
}
return 0;
}