Pagini recente » Cod sursa (job #2883880) | Cod sursa (job #730289) | Cod sursa (job #2507317) | Cod sursa (job #907399) | Cod sursa (job #2659425)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int N = 200000 + 7;
int n;
int m;
int step;
int d[N];
int dm[N];
int last[N];
vector<int> g[N];
vector<vector<int>> comps;
vector<pair<int, int>> edges;
bool eq(pair<int, int> a, pair<int, int> b) {
if (a == b) {
return 1;
}
swap(a.first, a.second);
return (a == b);
}
void dfs(int a, int p, int dep) {
int kids = 0;
d[a] = dm[a] = dep;
for (auto &b : g[a]) {
if (d[b] == -1) {
edges.push_back({a, b});
dfs(b, a, dep + 1);
dm[a] = min(dm[a], dm[b]);
kids++;
if (dep <= dm[b]) {
comps.push_back({});
while (1) {
assert(!edges.empty());
auto it = edges.back();
edges.pop_back();
comps.back().push_back(it.first);
comps.back().push_back(it.second);
if (eq(it, {a, b})) {
break;
}
}
}
continue;
}
if (d[b] >= d[a] - 1) {
continue;
}
edges.push_back({a, b});
dm[a] = min(dm[a], dm[b]);
}
}
int main() {
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
d[i] = -1;
}
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (d[i] == -1) {
dfs(i, -1, 0);
}
}
printf("%d\n", (int) comps.size());
for (auto &vec : comps) {
sort(vec.begin(), vec.end());
int y = -1;
for (auto &x : vec) {
if (x == y) {
continue;
}
y = x;
printf("%d ", x);
}
printf("\n");
}
}