Advertisement
Josif_tepe

Untitled

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