265
Cerința
Se dau cele n-1
muchii ale unui arbore cu n
noduri și un nod k
. Afișați vectorul de tați al arborelui cu rădăcina în k
.
Date de intrare
Fișierul de intrare arbore.in
conține pe prima linie numerele n k
, Următoarele n-1
linii vor conține câte o pereche i j
, reprezentând muchiile arborelui.
Date de ieșire
Fișierul de ieșire arbore.out
va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în k
, separate printr-un spațiu.
Restricții și precizări
1 ≤ n ≤ 100
1 ≤ k ≤ n
- în vectorul de tați rădăcina este marcată cu
0
Exemplu
arbore.in
7 4 1 2 1 4 1 7 3 7 5 7 6 7
arbore.out
4 1 7 0 7 7 1
#include <bits/stdc++.h> using namespace std; ifstream cin("arbore.in"); ofstream cout("arbore.out"); vector <int> G[101]; int n , p , x , y , T[102] , P[101]; void dfs(int x) { P[x] = 1; for(auto i:G[x]) if(!P[i]) { T[i] = x; dfs(i); } } int main() { cin >> n >> p; for(int i = 1 ; i < n ; i++) { cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } dfs(p); for(int i = 1 ; i <= n ; i++) cout << T[i] << " "; }
Comentarii