Pagini recente » Cod sursa (job #839707) | Cod sursa (job #356277) | Cod sursa (job #652726) | Cod sursa (job #1921708) | Cod sursa (job #3232720)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> graph;
vector<int> step;
vector<int> earliest;
int crtStep;
stack<pair<int, int>> edges;
vector<set<int>> components;
void init() {
int n, m;
fin >> n >> m;
graph = vector<vector<int>>(n + 1);
step = vector<int>(n + 1);
earliest = vector<int>(n + 1);
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
void getComponent(int node, int nextNode) {
components.emplace_back();
pair<int, int> top;
do {
top = edges.top();
edges.pop();
components.back().insert(top.first);
components.back().insert(top.second);
} while (top.first != node || top.second != nextNode);
}
void dfs(int node, int prevNode) {
earliest[node] = node;
for (const int nextNode : graph[node]) {
if (nextNode == prevNode) {
continue;
}
if (step[nextNode] != 0) {
earliest[node] = min(earliest[node], earliest[nextNode]);
continue;
}
step[nextNode] = ++crtStep;
edges.emplace(node, nextNode);
dfs(nextNode, node);
earliest[node] = min(earliest[node], earliest[nextNode]);
if (earliest[nextNode] >= step[node]) {
getComponent(node, nextNode);
}
}
}
int main() {
init();
for (size_t i = 1; i < graph.size(); ++i) {
if (step[i] == 0) {
step[i] = ++crtStep;
dfs(i, 0);
}
}
fout << components.size() << '\n';
for (const auto &component : components) {
for (int node : component) {
fout << node << ' ';
}
fout << '\n';
}
return 0;
}
// vim: ai et sw=4 ts=4