Question

Salutare, am o problema la care as avea nevoie de ajutor. Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine cel mai lung lanț elementar cu extremitățile p și q.
Exemplu
lantmaxim.in
5 7 1 4 1 3 3 5 4 5 1 2 4 2 3 4 2 5
lantmaxim.out
2 1 3 4 5
Chestia e ca pe acest exemplu si inca unul imi da, dar daca introduc, spre exemplu
8 10 1 2 1 3 2 3 2 8 3 4 3 7 4 5 5 6 6 7 7 8 8 4
Nu mai merge. orice ajutor e bine venit, va multumes anticipat

Answer 1

Nu stiu sigur prin ce metoda ai vrea tu sa fie rezolvata problema.

Banuiesc ca tu stii metoda backtracking din moment ce vrei sa parcurgi toate lanturile elementare dintr-un graf intre 2 noduri. Eu am facut o rezolvare cu backtracking, dar dupa ce am convertit informatiile furnizate din fisierul de intrare intr-o matrice de adiacenta binara unde am notat elementele matricei cu indici care au o muchie intre ei cu 1, si restul cu 0.
Folosindu-ma de acea matrice am generat apoi toate lanturile si l-am gasit pe cel mai lung. Poti sa vezi codul de mai jos in care incerc sa explic cat mai detaliat posibil:

#include <iostream>
#include <fstream>
#include <string.h>
#include <stdlib.h>
using namespace std;

int p,q,n,nr_muchii,adiacenta[20][20];
int max_lant=0,lant_actual;
string sol,s;
//ofstream fol("lantmaxim.out");

//determina numar varfuri
void nr_varfuri(){
ifstream fil("lantmaxim.in");
int nod,max=0,k=0;
while(fil>>nod){
if(nod>max){
max=nod;
}
k++;
}

//numarul de muchii este nr total de puncte fara ultimele 2 care sunt p si q
nr_muchii=(k-2)/2;
n=max;
}

//cream matricea de adiacenta
//aici determinam si p si q
void creare_matrice(){
ifstream fil("lantmaxim.in");
int i,a,b;
for(i=1;i<=nr_muchii;i++){
fil>>a>>b;
//graf neorientat, ambele muchii sunt incluse
adiacenta[a][b]=1;
adiacenta[b][a]=1;
}
fil>>p>>q;
}
//afisam matricea de adiacenta pentru teste
void afisare_adiacenta(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cout<<adiacenta[i][j]<<" ";
}
cout<<endl;
}
}

void back(int k){
int i,nr_muchii_ramase;
//buffer for conversion 1 char
char buffer[2];

for(i=1;i<=n;i++){

if(k==p){
lant_actual=1;
s=itoa(p,buffer,10);
}
//etapa de validare: daca elementul ales
//face parte dintr-o muchie, cauta dupa solutii
nr_muchii_ramase=0;
if(adiacenta[k][i]==1&&s.find(itoa(i,buffer,10))==s.npos){
//daca este valida, mareste lungime lant si adauga nod la string
//daca am gasit macar o muchie, inseamna ca o sa caut in acest arbor
nr_muchii_ramase=1;
lant_actual++;
s=s+itoa(i,buffer,10);
//etapa de gasire solutie: daca am ajuns la o muchie catre nodul q
//iar lungimea lantului gasit este mai mare decat lungimea lantului 
//de pana atunci, solutia devine sirul nou si opresc cautarea pe aceasta ramura
if(i==q&&lant_actual>max_lant){
max_lant=lant_actual;
sol=s;
break;

}
//altfel caut in continuare
else{
back(i);
}

}
//daca am ajuns la sfarsitul listei de noduri si nu mai am noduri ramase
//atunci elimina ultimul nod adaugat din cautare si reduce lungime lant
if(i==n&&nr_muchii_ramase==0){
s=s.substr(0,s.length()-1);
lant_actual--;
}


}
}


int main(){
int i;
ofstream fol("lantmaxim.out");
nr_varfuri();
cout<<"Nr de varfuri si de muchii sunt:";
cout<<n<<" "<<nr_muchii<<endl;
creare_matrice();
cout<<"Matricea de adiacenta este:"<<
afisare_adiacenta();
cout<<"Nodurile intre care trebuie sa caut sunt:";
cout<<p<<" "<<q<<endl;
back(p);
for(i=0;i<sol.length();i++){
fol<<sol[i]<<" ";
}
cout<<sol<<" "<<max_lant-1;
return 0;
}