Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5.  
  6. // EZ A PRÓBÁLKOZÁS NEM_MŰKÖDIK
  7. // ROSSZ_STRATÉGIA
  8.  
  9. struct Node
  10. {
  11.     bool is_visited = false;
  12.     bool store = false;
  13. };
  14.  
  15.  
  16. void BFS_store(std::vector<std::vector<int>>& graph, std::vector<Node>& visited, std::queue<int>& posqueue, std::queue<int> negqueue, int start)
  17. {
  18.     visited[start].is_visited = true;
  19.     if (visited[start].store)
  20.     {
  21.         for (int v : graph[start])
  22.         {
  23.             if (!visited[v].is_visited)
  24.             {
  25.                 visited[v].is_visited = true;
  26.                 negqueue.push(v);
  27.             }
  28.         }
  29.  
  30.     }
  31.     else
  32.     {
  33.         for (int v : graph[start])
  34.         {
  35.             if (!visited[v].is_visited)
  36.             {
  37.                 visited[v].is_visited = true;
  38.                 posqueue.push(v);
  39.                 visited[v].store = true;
  40.             }
  41.         }
  42.     }
  43.     if (negqueue.size() > 0)
  44.     {
  45.         int index = negqueue.front();
  46.         negqueue.pop();
  47.         BFS_store(graph, visited, posqueue, negqueue, index);
  48.     }
  49.     else if (posqueue.size() > 0)
  50.     {
  51.         int index = posqueue.front();
  52.         posqueue.pop();
  53.         BFS_store(graph, visited, posqueue, negqueue, index);
  54.     }
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60.  
  61.     int n;
  62.     std::cin >> n;
  63.     std::vector<std::vector<int>> graph(n);
  64.     std::vector<Node> visited(n);
  65.     for (int i = 0; i < n - 1; i++)
  66.     {
  67.         int a, b;
  68.         std::cin >> a >> b;
  69.         graph[a - 1].push_back(b - 1);
  70.         graph[b - 1].push_back(a - 1);
  71.     }
  72.     visited[0].store = true;
  73.     std::queue<int> posqueue;
  74.     std::queue<int> negqueue;
  75.     BFS_store(graph, visited, posqueue, negqueue, 0);
  76.  
  77.     std::vector<int> store1, store2;
  78.     for (size_t i = 0; i < visited.size(); i++)
  79.     {
  80.         if (visited[i].store)
  81.         {
  82.             store1.push_back(i + 1);
  83.         }
  84.         else
  85.         {
  86.             store2.push_back(i + 1);
  87.         }
  88.     }
  89.     if (store1.size() > store2.size())
  90.     {
  91.         std::cout << store1.size() << std::endl;
  92.         std::cout << store1[0];
  93.         for (size_t i = 1; i < store1.size(); i++)
  94.         {
  95.             std::cout << " " << store1[i];
  96.         }
  97.     }
  98.     else
  99.     {
  100.         std::cout << store2.size() << std::endl;
  101.         std::cout << store2[0];
  102.         for (size_t i = 1; i < store2.size(); i++)
  103.         {
  104.             std::cout << " " << store2[i];
  105.         }
  106.     }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement