Pagini recente » Cod sursa (job #307160) | Cod sursa (job #3277401) | Profil The_Viper_The_Mountain_And_The_Imp | Cod sursa (job #141605) | Cod sursa (job #3232703)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> graph;
vector<int> step;
int crtStep;
stack<pair<int, int>> edges;
vector<vector<int>> components;
void init() {
int n, m;
fin >> n >> m;
graph = vector<vector<int>>(n + 1);
step = 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().push_back(top.second);
} while (top.first != node && top.second != nextNode);
components.back().push_back(node);
}
int dfs(int node, int prevNode) {
int earliest = node;
for (const int nextNode : graph[node]) {
if (nextNode == prevNode) {
continue;
}
if (step[nextNode] != 0) {
earliest = min(earliest, step[nextNode]);
continue;
}
step[nextNode] = ++crtStep;
edges.emplace(node, nextNode);
const int nextEarliest = dfs(nextNode, node);
earliest = min(earliest, nextEarliest);
if (nextEarliest >= step[node]) {
getComponent(node, nextNode);
}
}
return earliest;
}
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