Pagini recente » Cod sursa (job #239197) | Cod sursa (job #234415) | Cod sursa (job #2513735) | Cod sursa (job #1300354) | Cod sursa (job #2790290)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int maxN = (int)1e5;
int n, m;
vector<int> g[maxN];
bool visited[maxN];
int l[maxN], d[maxN];
vector<pair<int, int>> edges;
vector<vector<int>> result;
void addBiconnected(int x, int y) {
result.push_back(vector<int>{});
while ((int)edges.size() > 0 && edges.back() != make_pair(x, y)) {
result.back().push_back(edges.back().first);
result.back().push_back(edges.back().second);
edges.pop_back();
}
result.back().push_back(edges.back().first);
result.back().push_back(edges.back().second);
edges.pop_back();
}
void dfs(int u, int cnt) {
visited[u] = true;
l[u] = d[u] = cnt;
cnt++;
for (int v : g[u]) {
if (!visited[v]) {
edges.emplace_back(u, v);
dfs(v, cnt);
l[u] = min(l[u], l[v]);
if (d[u] <= l[v]) {
addBiconnected(u, v);
}
} else {
l[u] = min(l[u], d[v]);
}
}
}
int main() {
in.tie(NULL);
out.tie(NULL);
in >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
in >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, cnt);
}
}
out << (int)result.size() << "\n";
for (vector<int> &comp : result) {
sort(comp.begin(), comp.end());
int lst = -1;
for (int u : comp) {
if (u != lst) {
out << u + 1 << " ";
}
lst = u;
}
out << "\n";
}
return 0;
}