Pagini recente » Cod sursa (job #922610) | Cod sursa (job #1988984) | Cod sursa (job #410243) | tema | Cod sursa (job #927323)
Cod sursa(job #927323)
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#define nmax 100005
using namespace std;
int m,rez,n,i,j,k,dfn[nmax],low[nmax],x,y,tata,nod,fiu;
vector<int>v[nmax],A[nmax];
stack<pair<int,int> >s;
void add(int nod,int tata)
{
rez++;
while (s.top().first!=nod && s.top().second!=tata)
{
A[rez].push_back(s.top().second);
s.pop();
}
A[rez].push_back(nod);
A[rez].push_back(tata);
s.pop();
}
void df(int nod,int tata)
{
int fiu;
dfn[nod]=low[nod]=dfn[tata]+1;
for (int j=0;j<v[nod].size();j++)
{
fiu=v[nod][j];
if (fiu!=tata)
{
if (!dfn[fiu])
{
s.push(make_pair(nod,fiu));
df(fiu,nod);
if (low[fiu]>=dfn[nod]) add(nod,fiu);
}
low[nod]=min(low[nod],low[fiu]);
}
}
}
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),v[x].push_back(y),v[y].push_back(x);
s.push(make_pair(1,0));
df(1,0);
printf("%d\n",rez);
for (i=1;i<=rez;i++)
{
for (j=0;j<A[i].size();j++)
printf("%d ",A[i][j]);
printf("\n");
}
return 0;
}