Pagini recente » Cod sursa (job #3311683) | Cod sursa (job #3356759) | Cod sursa (job #3344185) | Cod sursa (job #3341634) | Cod sursa (job #3306008)
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
int N, M;
vector<vector<int>> graph;
vector<int> low, level;
vector<bool> visited;
vector<vector<int>> result;
stack<pair<int, int>> edges;
void dfs(int node, int par) {
visited[node] = true;
for (auto& neighb : graph[node]) {
if (!visited[neighb]) {
level[neighb] = level[node] + 1;
edges.push({node, neighb});
dfs(neighb, node);
low[node] = min(low[node], low[neighb]);
if (low[neighb] >= level[node]) {
vector<int> comp;
while (!edges.empty()) {
comp.push_back(edges.top().second);
comp.push_back(edges.top().first);
edges.pop();
if (comp.back() == node) {
break;
}
}
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
result.push_back(comp);
}
} else if (neighb != par) {
low[node] = min(low[node], level[neighb]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M;
graph.assign(N + 1, vector<int>());
int from, to;
for (int idx = 0; idx < M; idx++) {
cin >> from >> to;
graph[from].push_back(to);
graph[to].push_back(from);
}
visited.assign(N + 1, false);
low.assign(N + 1, N);
level.assign(N + 1, 0);
stack<int> currEdges;
for (int idx = 0; idx < N; idx++) {
if (!visited[idx]) {
dfs(idx, -1);
}
}
cout << result.size() << "\n";
for (auto& comp : result) {
for (auto node : comp) {
cout << node << " ";
}
cout << "\n";
}
return 0;
}