Pagini recente » Cod sursa (job #1391467) | Cod sursa (job #1310300) | Cod sursa (job #321608) | Cod sursa (job #805827) | Cod sursa (job #2690819)
#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);
vector<tuple<int, int, int>> stk, comp;
function<int(int, int)> dfs = [&](int node, int pei) {
enter[node] = timer++;
int ret = enter[node];
for (auto itr : graph[node]) {
int vec, ei; tie(vec, ei) = itr;
if (ei == pei) continue;
if (enter[vec] != -1) {
ret = min(ret, enter[vec]);
if (enter[vec] < enter[node])
stk.emplace_back(node, vec, ei);
} else {
int sz = stk.size(), low = dfs(vec, ei);
ret = min(ret, low);
stk.emplace_back(node, vec, ei);
if (low >= enter[node]) {
comp = {stk.begin() + sz, stk.end()};
cb(comp); stk.resize(sz);
}
}
}
return ret;
};
for (int i = 0; i < (int)graph.size(); ++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<pair<int, int>>> graph(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b; --a; --b;
graph[a].emplace_back(b, i);
graph[b].emplace_back(a, i);
}
vector<vector<int>> comps;
BCC(graph, [&](vector<tuple<int, int, int>> comp) {
vector<int> v;
for (auto itr : comp) {
int a, b; tie(a, b, ignore) = itr;
v.push_back(a), v.push_back(b);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
comps.emplace_back(move(v));
});
cout << comps.size() << '\n';
for (auto comp : comps) {
for (auto x : comp)
cout << x + 1 << " ";
cout << '\n';
}
return 0;
}