Pagini recente » Cod sursa (job #1106697) | Cod sursa (job #2825012) | Cod sursa (job #1847187) | Cod sursa (job #1316454) | Cod sursa (job #2690822)
#include <bits/stdc++.h>
using namespace std;
template<typename Graph, typename CB>
void BCC(Graph& graph, CB cb) {
int timer = 0, n = graph.size();
vector<int> enter(n, -1), stk, comp;
function<int(int, int)> dfs = [&](int node, int par) {
enter[node] = timer++;
int ret = enter[node];
int sz = stk.size(); stk.push_back(node);
for (auto vec : graph[node]) {
if (vec == par) continue;
if (enter[vec] != -1) {
ret = min(ret, enter[vec]);
} else {
int low = dfs(vec, node);
ret = min(ret, low);
if (low >= enter[node]) {
comp = {stk.begin() + sz, stk.end()};
cb(comp); stk.resize(sz + 1);
}
}
}
return ret;
};
for (int i = 0; i < n; ++i)
if (enter[i] == -1)
dfs(i, -1);
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m; cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b; --a; --b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<vector<int>> comps;
BCC(graph, [&](vector<int> comp) {
comps.push_back(comp);
});
cout << comps.size() << '\n';
for (auto comp : comps) {
for (auto x : comp)
cout << x + 1 << " ";
cout << '\n';
}
return 0;
}