# PBinfo #4027 – LongestPath – Rezolvare C++

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

## Enunț

Se dă un graf orientat aciclic (adică nu există circuite). Lungimea unui drum elementar este dată de numărul de arce.

Cerința
Să se determine lungimea maximă a unui drum elementar în acest graf orientat aciclic.

Date de intrare
Programul citește de la tastatură numerele n și m, iar apoi m perechi de noduri i j cu semnificația: există în graf arcul cu extremitatea inițială în nodul i și extremitatea finală în nodul j.

Date de ieșire
Programul va afișa pe ecran un singur număr natural reprezentând lungimea maximă a unui drum elementar.

Restricții și precizări

3 ≤ n ≤ 100.000
3 ≤ m ≤ 200.000
Între două noduri va exista cel mult un arc
Nu există arc de la un nod la el însuși

Exemplu:
Intrare

7 9
4 1
5 4
5 1
1 3
1 2
2 6
6 3
7 1
1 6
Ieșire

5
Explicație
Cel mai lung drum este 5 4 1 2 6 3, graful din exemplu fiind ilustrat mai jos.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> L[100002];
int n, m, viz[100002], d[100002];
int sol[100002], len;
void Citire()
{
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        L[x].push_back(y);
    }
}
void DFS(int k)
{
    viz[k] = 1;
    for (int i : L[k])
        if (viz[i] == 0) DFS(i);
    sol[++len] = k;
}
void SortTop()
{
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0) DFS(i);
}
void LongestPath()
{
    int i, k, M;
    for (i = n; i >= 1; i--)
    {
        k = sol[i];
        for (int j : L[k])
            if (d[j] < 1 + d[k])
                d[j] = 1 + d[k];
    }
    M = 0;
    for (i = 1; i <= n; i++)
        if (M < d[i]) M = d[i];
    cout << M;
}
int main()
{
    Citire();
    SortTop();
    LongestPath();
    return 0;
}
```

## Resurse

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