Pagini recente » Cod sursa (job #3248464) | Cod sursa (job #2089084) | Cod sursa (job #1297254) | Cod sursa (job #329830) | Cod sursa (job #633153)
Cod sursa(job #633153)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
vector<vector<int> > rez;
stack<pair<int, int> > st;
vector<int> l[1001012];
int nrdf[101012], low[101012];
int n,m;
inline int minim(int a, int b)
{
return a<b?a:b;
}
void scoate(int x, int y)
{ vector<int> aux;
int aux1, aux2;
do{
aux1 = st.top().first;
aux2 = st.top().second;
st.pop();
aux.push_back(aux1);
aux.push_back(aux2);
}while(aux1 != x || aux2 != y);
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(),aux.end()),aux.end());
rez.push_back(aux);
}
void df(int nr, int pred , int lev)
{
nrdf[nr]=low[nr]=lev;
for( vector<int>::iterator it = l[nr].begin(); it != l[nr].end(); it++)
if(*it != pred)
{
if(nrdf[*it] == -1)
{ st.push(make_pair(nr,*it));
df(*it, nr, lev+1);
low[nr] = minim(low[nr], low[*it]);
if(low[*it] >= nrdf[nr])
scoate(nr, *it);
}
else low[nr] = minim(low[nr], low[*it]);
}
}
int main()
{ freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d", &n, &m);
int var1,var2;
for(int i = 0; i < m; i++)
{
scanf("%d%d", &var1, &var2);
l[var1].push_back(var2);
l[var2].push_back(var1);
}
for(int i=0; i<=n; i++)
nrdf[i]=-1;
df(1,0,0);
printf("%d\n", (int)rez.size());
for(int i=0; i< (int)rez.size(); i++)
{
for(vector<int>::iterator it = rez[i].begin(); it != rez[i].end(); it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}