Pagini recente » Cod sursa (job #2559959) | Cod sursa (job #2591060) | Cod sursa (job #688102) | Cod sursa (job #480922) | Cod sursa (job #265804)
Cod sursa(job #265804)
#include<stdio.h>
#include<stack>
#include<vector>
using namespace std;
FILE*fin=fopen("biconex.in","r");
FILE*fout=fopen("biconex.out","w");
#define nm 100005
#define pb push_back
#define mkp make_pair
#define x first
#define y second
vector<int>g[nm],ans[nm];
stack<pair<int,int> > stk;
int nrcb=0,level[nm],mlr[nm],used[nm],n,m;
void pmc(int a,int b)
{
int m1,m2;
nrcb++;
do
{
m1=stk.top().x;m2=stk.top().y;
stk.pop();
ans[nrcb].pb(m2);
}while(m1!=a||m2!=b);
ans[nrcb].pb(m1);
}
void df(int nod,int father)
{
int i,nnod;
level[nod]=level[father]+1;
mlr[nod]=level[nod];
for(i=0;i<g[nod].size();i++)
{
nnod=g[nod][i];
if(!used[nnod])
{
used[nnod]=1;
stk.push(mkp(nod,nnod));
df(nnod,nod);
if(mlr[nnod]<mlr[nod]) mlr[nod]=mlr[nnod];
if(mlr[nnod]>=level[nod]) pmc(nod,nnod);
}
else if(nnod!=father&&mlr[nnod]<mlr[nod]) mlr[nod]=mlr[nnod];
}
}
int main()
{
int a,b,i,j;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&a,&b);
g[a].pb(b);
g[b].pb(a);
}
memset(used,0,sizeof(used));
level[0]=0;used[1]=1;
df(1,0);
fprintf(fout,"%d\n",nrcb);
for(i=1;i<=nrcb;i++)
{
for(j=0;j<ans[i].size();j++)
fprintf(fout,"%d ",ans[i][j]);
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}