Pagini recente » Cod sursa (job #88478) | Cod sursa (job #2221194) | Cod sursa (job #1951455) | Cod sursa (job #55070) | Cod sursa (job #1758038)
#include <algorithm>
#include <fstream>
#include <functional>
#include <stack>
#include <vector>
using namespace std;
vector<vector<int>> biconex(vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<int> idx(graph.size(), -1);
vector<int> low(graph.size());
stack<pair<int, int>> st;
int index = 0;
function<vector<int>(pair<int, int>)>
make_component = [&](pair<int, int> edge) -> vector<int> {
vector<int> ans;
pair<int, int> current;
do {
current = st.top();
st.pop();
ans.push_back(current.first);
ans.push_back(current.second);
} while (edge != current);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
return ans;
};
function<void(int, int)>
dfs = [&](int node, int parent) {
idx[node] = low[node] = index ++;
for (int adj : graph[node]) {
if (adj == parent) continue;
if (idx[adj] == -1) {
st.push({node, adj});
dfs(adj, node);
low[node] = min(low[node], low[adj]);
if (low[adj] >= idx[node])
ans.push_back(make_component({node, adj}));
} else {
low[node] = min(low[node], idx[adj]);
}
}
-- index;
};
dfs(1, 0);
return ans;
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> graph;
int n, m;
fin >> n >> m;
graph.resize(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);
}
auto ans = biconex(graph);
fout << ans.size() << "\n";
for (auto comp : ans) {
for (int element : comp) {
fout << element << " ";
}
fout << "\n";
}
return 0;
}