Pagini recente » Cod sursa (job #1097570) | Cod sursa (job #1651469) | Cod sursa (job #2524317) | Cod sursa (job #1509570) | Cod sursa (job #288866)
Cod sursa(job #288866)
#include <fstream.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct lista
{
long nod;
lista *urm;
};
struct l2
{ /*lista dublu inlantuita: prec = pointer spre nodul precedent, urm = spre urmator*/
long x, y;
l2 *urm,*prec;
};
const int nmax = 100005;
const int nmax2 = 200005;
long n, m, tata[nmax], l[nmax], nivel[nmax], nr,biconexa[nmax];
lista *a[nmax2];
l2 *s, *sol[nmax2];
//******************LISTELE DE VECINI
//pun y in lista de vecini a lui x
void adaug_vecin(long x, long y)
{
lista *p;
p=new lista;
p->nod=y;
p->urm=NULL;
if (a[x])
p->urm=a[x];
a[x]=p;
}
//************************CONSTRUIREA SOLUTIEI sol[nr]=inceputul unei liste care retine solutia nr
//adaug la solutie muchia (x,y)
void adaug_sol(long x, long y)
{
l2 *d;
d=new l2;
d->x=x;
d->y=y;
d->urm=0;
d->prec=0;
if (sol[nr]!=0)
{
d->prec=sol[nr];
sol[nr]->urm=d;
}
sol[nr]=d;
}
//************************ELIMINAM O MUCHIE DIN STIVA S
// !!!!!!!!!!!!!!!!!!!!!!TRANSIMTEM CE AM ELIMINAT(VALOAREA LUI X SI Y)!!!!!!!!!!!!
//elimin muchia (x,y) din stiva
void elimin(long *x, long *y)
{
l2 *d;
d=new l2;
*x=s->x;
*y=s->y;
d=s;
s=s->prec;
delete d;
}
//**************************ADAUGAM ELEMENTE IN STIVA S
void adaug_stiva(long x, long y)
{
l2 *d;
d=new l2;
d->x=x;
d->y=y;
d->urm=NULL;//ambii pointeri (campuri de legatura)
d->prec=NULL; //ii initializez cu NULL
//adaug nodul d
if (s!=0) //daca s nu are elemente se va executa doar atribuirea s=d
{
d->prec=s;
s->urm=d;
}
s=d;
}
//*********************PARCURGEREA IN ADANCIME
//parcurgerea in adancime
void df(long k)
{
lista *p;
l2 *d;
long x,y;
l[k]=nivel[k];//initializez nivelul de care pot ajunge de la nodul k
//chiar cu nivelul pe care se afla in cazul parcurgerii df
for (p=a[k];p!=0;p=p->urm) //parcurg lista de vecini a lui k
// am declarat : "lista *a[nmax2];"
if (!tata[p->nod]) //daca nu este adaugat deja
{
adaug_stiva(k,p->nod);
tata[p->nod]=k;
nivel[p->nod]=nivel[k]+1;
df(p->nod); // functia se va autoapela fara a trece mai departe
// !!!!!!!!!!!!!!!instructiunile de mai jos se vor executa dar doar dupa ce se termina
//apelurile recursive df(p->nod) deci practic dupa ce sunt construiti vectorii: l,nivel,tata!!!!!!!
if (l[p->nod]<l[k]) l[k]=l[p->nod];//actualizez nivelul pe care pot ajunge din nodul k
if (l[p->nod]>=nivel[k]) //daca din p->nod nu pot ajunge mai sus de k
{
nr++; //am gasit o comp biconexa
do
{
elimin(&x,&y); //elimin muchie. x si y vor primi valori din functia elimin (ult element din stiva s)
adaug_sol(x,y);//adaug muchia la solutie
}
//pana cand stiva este goala sau am ajuns la muchia (k,p->nod)
while (s && (x!=k || y!=p->nod) && (x!=p->nod || y!=k));
}
}
else
if (p->nod!=tata[k] && nivel[p->nod]<l[k]) //daca p->nod nu este taticul lui k
l[k]=nivel[p->nod]; //si nivelul lui p->nod in cadrul parcurgeri df este mai mic decat nivelul pe
//care pot ajunge de la k atunci actualizez nivelul pe care pot ajunge de la k cu
//nivelul lui p->nod in cazul parcurgerii df
}
//**********main
int main()
{
long i,p1,p2,x,y;
f>>n>>m; //citirea din fisier si adaugarea muchiilor
for (i=1;i<=m;i++)
{
f>>p1>>p2;
adaug_vecin(p1,p2);
adaug_vecin(p2,p1);
}
//apelez parcurgerea in adancime df pentru fiecare nod
//daca graful este conex atunci df se apeleaza o singura data
//daca nu este conex se apeleaza pt fiecare componenta conexa
for (i=1;i<=n;i++)
if (!tata[i])
{
tata[i]=-1;
nivel[i]=1;
df(i);
}
g<<nr<<'\n';
//avem nr componente biconexe
for (i=1;i<=nr;i++)
{
do
{
y=sol[i]->y;
x=sol[i]->x;
if (biconexa[x]!=i)
{
g<<x<<" ";
biconexa[x]=i;
}
if (biconexa[y]!=i)
{
g<<y<<" ";
biconexa[y]=i;
}
sol[i]=sol[i]->prec;
}
while (sol[i]);
g<<'\n';
}
g.close();
return 0;
}