Pagini recente » Cod sursa (job #2748785) | Cod sursa (job #2667096) | Cod sursa (job #496012) | Cod sursa (job #2066378) | Cod sursa (job #632782)
Cod sursa(job #632782)
#include<iostream>
#include<fstream>
#include<stdio.h>
using namespace std;
#define MAX_N 100001
#define MAX_M 200001
struct lista
{
int nod;
lista *urm;
}*G[MAX_N];
int N, M, T[MAX_N], L[MAX_N], nv[MAX_N], st[MAX_M][2], lung, nr, v[MAX_N];
char U[MAX_N];
ofstream g("biconex.out",ios::out);
void push(int i, int j)
{
st[lung][0]=i;
st[lung++][1]=j;
}
void pop(int *i, int *j)
{
*i = st[--lung][0];
*j = st[lung][1];
}
void DF(int nod)
{
lista *p;
int x,y,i,j;
U[nod]=1;
L[nod]=nv[nod];
for(p=G[nod];p!=NULL;p=p->urm)
{
if(p->nod!=T[nod] && nv[nod]>nv[p->nod]) push(p->nod,nod);
if(!U[p->nod])
{
nv[p->nod] = nv[nod]+1;
T[p->nod] = nod;
DF(p->nod);
if(L[nod]>L[p->nod]) L[nod]=L[p->nod];
if(L[p->nod]>=nv[nod])
{
pop(&x,&y);
v[1]=x; v[2]=y; i=3;
while( (x!=nod || y!=p->nod) && (x!=p->nod || y!=nod) )
{pop(&x,&y); v[i]=y; i++;
}
for(j=1;j<=i-2;j++) g<<v[j]<<" ";
if(v[1]!=v[i-1])g<<v[i-1];
g<<endl; nr++;
}
}
else if(p->nod!=T[nod] && L[nod]>nv[p->nod])
L[nod]=nv[p->nod];
}
}
int main (void)
{
ifstream f("biconex.in");
g<<endl;
lista *p;
int x,y,i;
f>>N>>M;
for(i=1;i<=M;i++)
{
f>>x>>y;
p=new lista;
p->urm = G[x];
p->nod = y;
G[x]=p;
p=new lista;
p->urm = G[y];
p->nod = x;
G[y]=p;
}
f.close();
for(i=N;i>=1;i--)
if(!U[i]) {nv[i]=1; DF(i);}
g.seekp(0,ios::beg);
g<<nr;
g.close();
return 0;
}