Pagini recente » Cod sursa (job #3315743) | Cod sursa (job #2573597) | Cod sursa (job #1528752) | Cod sursa (job #1220280) | Cod sursa (job #3306000)
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
int N, M;
vector<vector<int>> graph;
vector<int> low;
vector<bool> visited;
vector<vector<int>> result;
stack<pair<int, int>> edges;
void dfs(int node, int par, int level) {
visited[node] = true;
low[node] = level;
for (auto& neighb : graph[node]) {
if (!visited[neighb]) {
edges.push({node, neighb});
dfs(neighb, node, level + 1);
low[node] = min(low[node], low[neighb]);
if (low[neighb] >= level) {
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], low[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);
stack<int> currEdges;
for (int idx = 0; idx < N; idx++) {
if (!visited[idx]) {
dfs(idx, -1, 0);
}
}
cout << result.size() << "\n";
for (auto& comp : result) {
for (auto node : comp) {
cout << node << " ";
}
cout << "\n";
}
return 0;
}