Jump to content
HiDinjection

Problema C++ graf orientat

Recommended Posts

Posted

Se da urmatoarea problema:

Se citeste un graf orientat cu n varfuri si m arce prin lista arcelor. Se da numar natural k mai mic decat n si k varfuri ale grafului.

Afisati toate drumurile elementare care au ca extremitate initiala varful 1, ca extremitate finala varful n si care trec prin cele k varfuri citite in ordinea in care au fost citite.

Rezolvare:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int A[50][50],n,m,k;
int x[50],p[50],pus[50],b[50];

void afis(int n)
{
for(int i=1;i<=n;i++) fout<<x[i]<<" ";
fout<<endl;
}

int bun(int pas)
{
if(p[x[pas]]>=2)
for(int i=1;i<=k;i++)
if(p[b[i]]>0 && p[b[i]]<p[x[pas]] && !pus[b[i]]) return 0;
return 1;
}

int sol(int pas)
{
for(int i=1;i<=k;i++)
if(!pus[b[i]]) return 0;
return 1;
}

void back(int k, int pas)
{
for(int i=1;i<=n;i++)
if(!pus[i] && A[x[pas-1]][i])
{
x[pas]=i;
pus[i]=1;
if(bun(pas))
if(x[pas]==n && sol(pas)) afis(pas);
else back(k,pas+1);
pus[i]=0;
}
}

int main()
{
int v1,v2;
fin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
fin>>v1>>v2;
A[v1][v2]=1;
}
for(int i=1;i<=k;i++)
{
fin>>b[i];
p[b[i]]=i;
}
x[1]=1;
pus[1]=1;
back(k,2);
fin.close();
fout.close();
return 0;
}

Imi poate explica cineva problema in detaliu? functiile sol, bun si back... nu inteleg de ce trebuie sa returneze valoarea 0 respectiv 1 si cand ... o are de explicat o cunostiinta sa treaca un examen :) multumesc anticipat!

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...