253
Cerința
Se dă mulțimea V
a arcelor unui graf orientat cu n
vârfuri.
Exemplu
dslm.in
12 2 1 2 2 3 3 1 1 4 6 4 4 5 5 7 7 5 8 9 9 8 10 11 11 12
dslm.out
2 3 1 4 5 7 5
Explicație
Graful conține un singur drum simplu de lungime maximă cu extremitatea inițială în vârful p=2
, D=[2,3,1,4,5,7,5]
#include <bits/stdc++.h> using namespace std; ifstream cin("dslm.in"); ofstream cout("dslm.out"); int n , a[25][25] , x1 , y , x[25] , p[25] , P , kmax , re[101]; void afisare(int k) { for(int i = 1 ; i <= k ; i++) cout << x[i] << " "; cout << '\n'; } void rez(int k) { for(int i = 1 ; i <= k ; i++) re[i] = x[i]; } void back(int k) { for(int i = 1 ; i <= n ; i++) { x[k] = i; if(a[x[k - 1]][x[k]] == 1) { a[x[k - 1]][x[k]] = 0; if(k > kmax) kmax = k , rez(k); back(k + 1); a[x[k - 1]][x[k]] = 1; } } } int main() { cin >> n >> P; while(cin >> x1 >> y) a[x1][y] = 1; x[1] = P; p[P] = 1; back(2); for(int i = 1 ; i <= kmax ; i++) cout << re[i] << " "; }
Comentarii