Pagini recente » Cod sursa (job #2067662) | Cod sursa (job #919350) | Cod sursa (job #2478563) | Cod sursa (job #1915236) | Cod sursa (job #3202115)
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
vector<int> graf[N];
int n, m;
int depth[N];
bool visited[N];
int maxheight[N];
void dfs1(int x) {
visited[x] = true;
for (int muchie : graf[x]) {
if (!visited[muchie]) {
depth[muchie] = depth[x] + 1;
dfs1(muchie);
}
}
}
int nr = 0;
vector<int> stiva;
vector<vector<int>> ans;
void dfs2(int x, int parent = 0) {
visited[x] = true;
stiva.push_back(x);
for (int muchie : graf[x]) {
if (!visited[muchie]) {
dfs2(muchie, x);
maxheight[x] = min(maxheight[muchie], maxheight[x]);
if (maxheight[muchie] >= depth[x]) {
nr++;
ans.push_back({});
while (stiva.back() != x) {
ans.back().push_back(stiva.back());
stiva.pop_back();
}
ans.back().push_back(stiva.back());
}
}
else {
if (muchie != parent)
maxheight[x] = min(maxheight[muchie], maxheight[x]);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
maxheight[i] = -1;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
dfs1(1);
for (int i = 1; i <= n; i++) {
visited[i] = false;
maxheight[i] = depth[i];
}
dfs2(1);
cout << nr << '\n';
for (vector<int>& componenta : ans) {
for (int nod : componenta) {
cout << nod << ' ';
}
cout << '\n';
}
return 0;
}