Pagini recente » Cod sursa (job #1265494) | Cod sursa (job #2789059) | Cod sursa (job #1095842) | Cod sursa (job #3132166) | Cod sursa (job #632771)
Cod sursa(job #632771)
#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;
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;
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);
g<<x<<" "<<y;
while( (x!=nod || y!=p->nod) && (x!=p->nod || y!=nod) )
{pop(&x,&y); g<<" "<<y;}
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=1;i<=N;i++)
if(!U[i]) {nv[i]=1; DF(i);}
g.seekp(0,ios::beg);
g<<nr;
g.close();
return 0;
}