Pagini recente » Monitorul de evaluare | Cod sursa (job #1431476) | Monitorul de evaluare | Cod sursa (job #1431353) | Cod sursa (job #2681648)
#include <fstream>
#include <stack>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
ifstream fin{"biconex.in"};
ofstream fout{"biconex.out"};
int n, m;
fin >> n >> m;
vector<vector<int>> graph(n);
for (auto i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
graph[x - 1].emplace_back(y - 1);
graph[y - 1].emplace_back(x - 1);
}
vector<int> indexes(n, -1);
vector<int> lowlinks(n);
vector<unordered_set<int>> components;
stack<pair<int, int>> st;
auto last_index = -1;
auto tarjan = [&](int node, auto &&f) -> void {
indexes[node] = lowlinks[node] = ++last_index;
for (auto neigh : graph[node]) {
if (indexes[neigh] == -1) {
// Recurse on neigh.
st.emplace(node, neigh);
f(neigh, f);
// Update lowlink.
lowlinks[node] = min(lowlinks[node], lowlinks[neigh]);
// Pop component if needed.
if (lowlinks[neigh] >= indexes[node]) {
unordered_set<int> comp;
int child, parent;
do {
comp.emplace((parent = st.top().first));
comp.emplace((child = st.top().second));
st.pop();
} while (parent != node || child != neigh);
components.emplace_back(comp);
}
} else {
lowlinks[node] = min(lowlinks[node], indexes[neigh]);
}
}
};
for (auto i = 0; i < n; ++i)
if (indexes[i] == -1) {
tarjan(i, tarjan);
}
fout << components.size() << '\n';
for (auto &&comp : components) {
for (auto e : comp) {
fout << e + 1 << ' ';
}
fout << '\n';
}
}