Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Date de intrare

Fişierul de intrare ciclu.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Următoarea linie conține numărul p.

Date de ieşire

Fişierul de ieşire ciclu.out va conține un singur ciclu elementar care conține vârful p. Acesta va începe și se va termina cu vârful p.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ i , j ≤n
• muchiile se pot repeta în fișierul de intrare
• 1 ≤ p ≤ n
• pentru toate datele de test, va exista cel puțin un ciclu care conține vârful p

Exemplu

ciclu.in

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2

ciclu.out

2 1 3 4 2

#include <bits/stdc++.h>

using namespace std;

ifstream cin("ciclu.in");
ofstream cout("ciclu.out");

vector <int>G[101];

int n , m , x , y , P[30] , X[30] , p , ok;

void afisare(int k)
{
    for(int i = 1 ; i <= k ; i++)
        cout << X[i] << " ";
    cout << '\n';
    ok = 1;
}

int oke(int k)
{
    int ok = 0;
    for(auto x:G[X[k]])
        if(x == X[k - 1]) ok++;
    if(ok != 0)return 1;
    else return 0;
}

void back(int k)
{
    for(int i = 1 ; i <= n && !ok; i++)
        if(!P[i])
        {
            P[i] = 1;
            X[k] = i;
            if(oke(k))
                if(X[k] == p && k > 3)afisare(k);
                else back(k + 1);
            P[i] = 0;
        }
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cin >> p;
    X[1] = p;
    back(2);
}