# PBinfo #476 – Lanturi – 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 trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care conțin vârful r.

Date de intrare
Fişierul de intrare lanturi.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 trei numere p q r, cu semnificația precizată.

Date de ieşire
Fişierul de ieşire lanturi.out va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în p, respectiv q, care conțin vârful r, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.

Restricţii şi precizări

1 ≤ n ≤ 20
1 ≤ i , j ≤n
muchiile se pot repeta în fișierul de intrare
1 ≤ p , q , r ≤ n
p, q și r sunt diferite

Exemplu:
lanturi.in

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2 5 3
lanturi.out

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

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("lanturi.in");
ofstream fout("lanturi.out");
int n , a[105][105], x[205] , p , q , r;
void afis(int k)
{
	for(int  i = 1 ; i <= k ; ++ i)
		fout << x[i] << " ";
	fout << "\n";
}
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 , int pus_r)
{
	for(int i = 1  ; i <= n ; ++i)
	{
		x[k] = i;
		if(OK(k))
		{
			if(x[k] == r)
				pus_r = 1;
			if(x[k] == q)
			{
				if( pus_r )
					afis(k);
			}
			else
				back(k + 1, pus_r);
			if(x[k] == r)
				pus_r = 0;
		}
	}
}
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 >> q >> r);
	x[1] = p;
	back(2 , 0);
	return 0;
}
```

## Resurse

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