# PBinfo #4290 – GasesteCiclu – Rezolvare C++

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

## Enunț

Cerința
Se dă un graf neorientat cu n vârfuri numerotate de la 1 la n și m muchii. Știind că graful are cel puțin un ciclu, să se determine un ciclu elementar în acest graf.

Date de intrare
Programul citește de la tastatură numerele n m, apoi se citesc m perechi de numere i j cu semnificația: există în graf muchia (i, j).

Date de ieșire
Programul va afișa pe ecran un ciclu din graf. Dacă există mai multe cicluri elementare, se va afișa unul singur.

Restricții și precizări

1 ≤ n ≤ 100
Graful are cel puțin un ciclu.
Muchiile sunt distincte și între orice două vârfuri poate exista cel mult o muchie.

Exemplu:
Intrare

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

2 7 5 4 2
Explicație
Graful are ciclul 2 7 5 4 2. O altă soluție care se putea afișa era și 6 3 9 6.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[105][105], n, m, viz[105], pred[105];
void Citire()
{
    int i, j, k;
    cin >> n >> m;
    assert(1 <= n && n <= 100);
    for (k = 1; k <= m; k++)
    {
        cin >> i >> j;
        assert(1 <= i && i <= n);
        assert(1 <= j && j <= n);
        assert(i != j);
        a[i][j] = a[j][i] = 1;
    }
}
void Afis(int k, int i)
{
    cout << i << " ";
    while (k != i)
    {
        cout << k << " ";
        k = pred[k];
    }
    cout << i << "\n";
    exit(0);
}
void DFS(int k)
{
    viz[k] = 1;
    for (int i = 1; i <= n; i++)
        if (a[k][i] == 1)
        {
            if (viz[i] == 0)
            {
                pred[i] = k;
                DFS(i);
            }
            else
            {
                if (i != pred[k])
                    Afis(k, i);
            }
        }
}
void Rezolva()
{
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0) DFS(i);
}
int main()
{
    Citire();
    Rezolva();
    return 0;
}
```

## Resurse

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