Advertisement
Josif_tepe

Untitled

Oct 20th, 2024
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 100005;
  6. vector<int> graph[maxn];
  7.  
  8. vector<int> bfs(int S) {
  9.     vector<int> path;
  10.    
  11.     vector<bool> visited(maxn, false);
  12.     visited[S] = true;
  13.     queue<int> q;
  14.     q.push(S);
  15.    
  16.     while(!q.empty()) {
  17.         int node = q.front();
  18.         q.pop();
  19.        
  20.         path.push_back(node);
  21.        
  22.         for(int neighbour : graph[node]) {
  23.             if(!visited[neighbour]) {
  24.                 visited[neighbour] = true;
  25.                 q.push(neighbour);
  26.             }
  27.         }
  28.  
  29.     }
  30.     return path;
  31. }
  32.  
  33. int main() {
  34.     int k;
  35.     cin >> k;
  36.    
  37.     for(int i = 1; i < k; i++) {
  38.         int a, b;
  39.         cin >> a >> b;
  40.         graph[a].push_back(b);
  41.         graph[b].push_back(a);
  42.     }
  43.    
  44.     vector<int> p1 = bfs(0);
  45.    
  46.     for(int i = 0; i < p1.size(); i++) {
  47.         cout << p1[i] << " " ;
  48.     }
  49.    
  50.     vector<int> p2 = bfs(k);
  51.     for(int i = (int) p2.size() - 1; i >= 0; i--) {
  52.         cout << p2[i] << " ";
  53.     }
  54.     return 0;
  55. }
  56.  
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement