Pagini recente » Cod sursa (job #2081881) | Cod sursa (job #2736391) | Cod sursa (job #1852339) | Cod sursa (job #1586488) | Cod sursa (job #1706358)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000;
const int MMAX = 200000;
int dp[NMAX+5];
vector <int> v[NMAX+5];
int h[NMAX+5];
bool f[NMAX+5];
stack <int> st;
int NR;
vector <int> ans[MMAX+5];
void dfs(int nod)
{
dp[nod] = h[nod];
for(int i=0; i<v[nod].size(); i++)
{
if(h[v[nod][i]] == 0)
{
h[v[nod][i]] = h[nod]+1;
dfs(v[nod][i]);
dp[nod] = min(dp[nod], dp[v[nod][i]]);
}
else dp[nod] = min(dp[nod], h[v[nod][i]]);
}
}
void biconex(int nod)
{
for(int i=0; i<v[nod].size(); i++)
if(!f[v[nod][i]])
{
st.push(v[nod][i]);
f[v[nod][i]] = true;
biconex(v[nod][i]);
if(dp[v[nod][i]] >= h[nod])
{
while(st.top()!=nod)
{
ans[NR].push_back(st.top());
st.pop();
}
ans[NR].push_back(nod);
NR++;
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for(int i=0; i<m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
x--;y--;
v[x].push_back(y);
v[y].push_back(x);
}
h[0] = 1;
dfs(0);
f[0] = 1;
st.push(0);
biconex(0);
printf("%d\n", NR);
for(int i=0; i<NR; i++)
{
for(int j=0; j<ans[i].size(); j++)
printf("%d ", ans[i][j]+1);
printf("\n");
}
return 0;
}