Pagini recente » Cod sursa (job #1492839) | Cod sursa (job #3129508) | Cod sursa (job #1751667) | Cod sursa (job #2290171) | Cod sursa (job #2719455)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
const int N = 1e5 + 5;
int timp = 1, n, m, top, nrc;
int l[N], viz[N], stiva[N];
bool art[N];
vector <int> v[N], ans[N];
void dfs(int nod, int last) {
viz[nod] = l[nod] = timp;
int fii = 0;
for (auto it : v[nod]) {
if (!viz[it]) {
++timp;
dfs(it, nod);
++fii;
if (nod != 1 && l[it] >= viz[nod] || nod == 1 && fii > 1) {
art[nod] = true;
}
}
if (it != last)
l[nod] = min(l[nod], l[it]);
}
}
void dfs2(int nod, int last) {
viz[nod] = -1;
stiva[++top] = nod;
for (auto it : v[nod]) {
if (viz[it] != -1) {
dfs2(it, nod);
if (art[nod]) {
++nrc;
ans[nrc].push_back(nod);
while (stiva[top] != nod)
ans[nrc].push_back(stiva[top--]);
sort (ans[nrc].begin(), ans[nrc].end());
}
}
}
}
int main() {
cin >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
dfs2(1, 0);
cout << nrc << '\n';
for (int i = 1; i <= nrc; ++i) {
for (auto it : ans[i])
cout << it << ' ';
cout << '\n';
}
return 0;
}