Jump to content
HiDinjection

Problema C++ graf orientat

Recommended Posts

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!

Link to comment
Share on other sites

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...