Pagini recente » Cod sursa (job #2139823) | Cod sursa (job #2976515) | Cod sursa (job #783240) | Cod sursa (job #1012195) | Cod sursa (job #548579)
Cod sursa(job #548579)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int nmax = 100005;
vector <int> G[nmax],sol[10005];
vector <int>::iterator it;
stack < pair<int, int> > S;
int n,m,k,i,x,y,u,nv[nmax],L[nmax];
void salveaza(int x, int y)
{
int p,u;
k++;
do{
p=S.top().first;
u=S.top().second;
S.pop();
sol[k].push_back(p);
sol[k].push_back(u);
}while (p!=x || u!=y);
}
void df(int nod, int tata, int adanc)
{
vector<int>::iterator it;
nv[nod]=L[nod]=adanc;
for(it=G[nod].begin();it!=G[nod].end();++it)
{
if(*it!=tata)
if(nv[*it])
L[nod]=min(L[nod],nv[*it]);
else
{
S.push(make_pair(nod,*it));
df(*it,nod,adanc+1);
L[nod]=min(L[nod],L[*it]);
if(L[*it]>=nv[nod])
salveaza(nod,*it);
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;i++)
{
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
df(1,-1,1);
printf("%d\n", k);
for (i=1;i<=k;i++)
{
sort(sol[i].begin(), sol[i].end());
for (it=sol[i].begin();it!=sol[i].end();it++)
if(*it!=u)
printf("%d ", (u=*it));
printf("\n");
}
return 0;
}