Pagini recente » Cod sursa (job #822642) | Cod sursa (job #1751030) | Cod sursa (job #647454) | Cod sursa (job #1042480) | Cod sursa (job #1236432)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
#define INF 999999999
using namespace std;
int n, m;
int h[100010], hmin[100010], viz[100010];
vector<int> vec[100010];
vector<vector<int> > sol;
vector<int> s;
void citire()
{
int x, y, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
vec[x].push_back(y);
vec[y].push_back(x);
}
}
void adsol(int x)
{
vector<int> newsol;
newsol.clear();
while(s.back() != x)
{
newsol.push_back(s.back());
s.pop_back();
}
newsol.push_back(x);
// s.pop_back();
sol.push_back(newsol);
}
int solve(int x = 1, int tata = 0)
{
s.push_back(x);
viz[x] = 1;
hmin[x] = h[x] = h[tata] + 1;
int neviz = 0;
for(int i = 0; i < vec[x].size(); i++)
{
if(!viz[vec[x][i]])
{
if(neviz)
s.push_back(x);
neviz++;
solve(vec[x][i], x);
hmin[x] = min(hmin[x], hmin[vec[x][i]]);
if(hmin[vec[x][i]] >= h[x])
{
adsol(x);
if(neviz > 1)
s.pop_back();
}
}
else if(vec[x][i] != tata)
hmin[x] = min(hmin[x], h[vec[x][i]]);
}
}
void afisare()
{
printf("%d\n", sol.size());
for(int i = 0; i < sol.size(); i++, printf("\n"))
for(int j = 0; j < sol[i].size(); j++)
printf("%d ", sol[i][j]);
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}