# PBinfo #1551 – DSLM – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Se dă mulțimea V a arcelor unui graf orientat cu n vârfuri.

Cerința
Să se determine drumul simplu de lungime maximă cu extremitatea inițială în vârful p din graf. Un drum simplu parcurge o singură dată un arc de pe traseul descris de drum în graf.

Date de intrare
Fișierul de intrare dslm.in conține pe prima linie numerele n și p, iar pe fiecare din următoarele linii, câte două numere a b reprezentând câte un arc (a,b) din V.

Date de ieșire
Fișierul de ieșire dslm.out va conține pe prima linie cel mai mic drum în sens lexicografic dintre drumurile simple de lungime maximă cu extremitatea inițială în nodul p; vârfurile din drum sunt separate prin câte un singur spațiu.

Restricții și precizări

1 ≤ n ≤ 20
1 ≤ a , b ≤n
1 ≤ p ≤ n
mulțimea V are cel mult 30 de elemente
pentru fiecare test există soluție
dacă există mai multe soluții, atunci se va scrie în fișier cel mai mic drum în sens lexicografic dintre soluțiile obținute

Exemplu:
dslm.in

12 2
1 2
2 3
3 1
1 4
6 4
4 5
5 7
7 5
8 9
9 8
10 11
11 12
dslm.out

2 3 1 4 5 7 5
Explicație
Graful conține un singur drum simplu de lungime maximă cu extremitatea inițială în vârful p=2, D=[2,3,1,4,5,7,5]

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("dslm.in");
ofstream g("dslm.out");
int a[21][21],n,p, d[100], dmax[100],lgmax;
void citire()
{
    int i,x,y;
    f>>n>>p;
    while(f>>x>>y)
        a[x][y]=1;
}
void copie(int lg)
{
    lgmax=lg;
    for(int i=1; i<=lg; i++) dmax[i]=d[i];
}
void scrie_drum()
{
    for(int i=1; i<=lgmax; i++)
        g<<dmax[i]<<" ";
    g<<endl;
}
void dfs(int x, int lg)
{
    d[lg]=x;
    int ex_s=0, y;
    for(y=1; y<=n; y++)
        if(a[x][y])
        {
            a[x][y]=0;
            ex_s=1;
            dfs(y,lg+1);
            a[x][y]=1;
        }
    if(ex_s==0 && lg>lgmax)
        copie(lg);
}
int main()
{
    citire();
    dfs(p,1);
    scrie_drum();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1551)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1551/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1551/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)