# PBinfo #478 – Ciclu – Rezolvare C++

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

## Enunț

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

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("ciclu.in");
ofstream fout("ciclu.out");
int n , a[105][105], x[205] , p, gasit = 0;
void afis(int k)
{
	for(int  i = 1 ; i <= k ; ++ i)
		fout << x[i] << " ";
	fout << p << "\n";
	gasit = 1;
}
int OK(int k)
{
	if(a[x[k-1]][x[k]] != 1)
		return 0;
	for(int i = 1 ; i < k ; ++i)
		if( x[k] == x[i] )
			return 0;
	return 1;
}
void back(int k)
{
	for(int i = 1  ; i <= n && ! gasit ; ++i)
	{
		x[k] = i;
		if(OK(k))
		{
			if( a[x[k]][p] == 1 && k > 2 )
				afis(k);
			back(k + 1);
		}
	}
}
int main()
{
    int i , j , m;
    fin >> n >> m;
    while(m > 0)
    {
		fin >> i >> j;
    	a[i][j] = a[j][i] = 1;
    	m --;
    }
	assert(fin >> p);
	x[1] = p;
	back(2);
	return 0;
}
```

## Resurse

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