Pagini recente » Cod sursa (job #367846) | Cod sursa (job #1454208) | Cod sursa (job #2928239) | Cod sursa (job #36487) | Cod sursa (job #720841)
Cod sursa(job #720841)
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
#define NMAX 100005
FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");
struct muchie { long x,y;};
stack<muchie> S;
vector<long> L[NMAX],sol[NMAX];
long n,m, nv[NMAX] , mn[NMAX], T[NMAX],viz[NMAX],nr;
void afis(long a,long b)
{
nr++;
sol[nr].push_back(S.top().y);
while (S.top().x!=a && S.top().y!=b)
{ sol[nr].push_back(S.top().x);
S.pop();
}
sol[nr].push_back( S.top().x );
S.pop();
}
void df(long nod)
{
mn[nod]=nv[nod];
viz[nod]=1;
for (long i=0;i<L[nod].size();i++)
if (!viz[ L[nod][i] ] )
{
T [ L[nod][i] ] = nod;
nv[ L[nod][i] ] = nv[nod]+1;
muchie mc;
mc.x=nod; mc.y = L[nod][i];
S.push(mc);
df( L[nod][i] );
if ( mn[ L[nod][i] ] <mn[nod] ) mn[nod] = mn[L[nod][i]];
if ( mn[ L[nod][i] ] >= nv[nod] ) afis(nod,L[nod][i]);
}
else if (nv[ L[nod][i] ] < mn [nod] && L[nod][i]!=T[nod] ) mn[nod]=nv[ L[nod][i] ];
}
int main()
{
fscanf(f,"%ld%ld",&n,&m);
for (long i=1;i<=m;i++)
{ long a,b;
fscanf(f,"%ld%ld",&a,&b);
L[a].push_back(b);
L[b].push_back(a);
}
nv[1]=1;
df(1);
fprintf(g,"%ld\n",nr);
for (long i=1;i<=nr;i++)
{ for (long j=0;j<sol[i].size();j++)
fprintf(g,"%ld ",sol[i][j]);
fprintf(g,"\n");
}
return 0;}