Nik_Perepelov

доп контест Елена

Nov 17th, 2021 (edited)
294
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class Task {
  7.     vector<int> size;
  8.     vector<int> set_parent_2007;
  9.     vector<vector<int>> kitties;
  10.  
  11. public:
  12.     Task();
  13.  
  14.      Task(int n) {
  15.          set_parent_2007 = vector<int>(n);
  16.         size = vector<int>(n, 1);
  17.         kitties = vector<vector<int>>(n);
  18.         for (int i = 0; i < n; i++) {
  19.             set_parent_2007[i] = i;
  20.             kitties[i].emplace_back(i + 1);
  21.         }
  22.     }
  23.  
  24.     int get_set(int v) {
  25.         if (set_parent_2007[v] == v)
  26.             return v;
  27.         return set_parent_2007[v] = get_set(set_parent_2007[v]);
  28.     }
  29.    
  30.     void my_swap(int &a, int &b){
  31.          int tmp = a;
  32.          a = b;
  33.          b = tmp;
  34.      }
  35.  
  36.     void join_sets(int set1, int set2) {
  37.         set1 = get_set(set1);
  38.         set2 = get_set(set2);
  39.         if (set1 != set2) {
  40.             if (size[set1] < size[set2]) {
  41.                 my_swap(set1, set2);
  42.             }
  43.  
  44.             set_parent_2007[set2] = set1;
  45.             size[set1] += size[set2];
  46.  
  47.             kitties[set1].insert(kitties[set1].end(), kitties[set2].begin(), kitties[set2].end());
  48.             kitties[set2].clear();
  49.         }
  50.     }
  51.  
  52.     vector<int> get_content(){
  53.         return kitties[get_set(0)];
  54.     }
  55. };
  56.  
  57.  
  58. int main() {
  59.     int n;
  60.     cin >> n;
  61.     Task task(n);
  62.     for (int i = 0; i < n - 1; i++){
  63.         int v1, v2;
  64.         cin >> v1 >> v2;
  65.         task.join_sets(v1 - 1, v2 - 1);
  66.     }
  67.     vector<int> answer = task.get_content();
  68.     for (int i = 0; i < answer.size(); i++)
  69.         cout << answer[i] << ' ';
  70.  
  71.     return 0;
  72. }
  73.  
  74.  
  75. //
  76. // 4
  77.  
  78. //
  79. #include <iostream>
  80. #include <vector>
  81.  
  82. using namespace std;
  83.  
  84. class Task {
  85.     vector<int> size;
  86.     vector<int> set_parent_2007;
  87.     vector<vector<int>> kitties;
  88.     int k = 0;
  89.  
  90. public:
  91.     Task();
  92.  
  93.      Task(int n) {
  94.          k = n;
  95.          set_parent_2007 = vector<int>(n);
  96.         size = vector<int>(n, 1);
  97.         kitties = vector<vector<int>>(n);
  98.         for (int i = 0; i < n; i++) {
  99.             set_parent_2007[i] = i;
  100.             kitties[i].emplace_back(i + 1);
  101.         }
  102.     }
  103.  
  104.     int get_set(int v) {
  105.         if (set_parent_2007[v] == v)
  106.             return v;
  107.         return set_parent_2007[v] = get_set(set_parent_2007[v]);
  108.     }
  109.  
  110.     void my_swap(int &a, int &b){
  111.          int tmp = a;
  112.          a = b;
  113.          b = tmp;
  114.      }
  115.  
  116.     void join_sets(int set1, int set2) {
  117.         set1 = get_set(set1);
  118.         set2 = get_set(set2);
  119.         if (set1 != set2) {
  120.             if (size[set1] < size[set2]) {
  121.                 my_swap(set1, set2);
  122.             }
  123.  
  124.             set_parent_2007[set2] = set1;
  125.             size[set1] += size[set2];
  126.  
  127.             kitties[set1].insert(kitties[set1].end(), kitties[set2].begin(), kitties[set2].end());
  128.             kitties[set2].clear();
  129.             k--;
  130.         }
  131.     }
  132.  
  133.     int get_content(){
  134.         return k;
  135.     }
  136. };
  137.  
  138.  
  139. int main() {
  140.     int n;
  141.     cin >> n;
  142.     Task a(n);
  143.     for (int i = 0; i < n; i++){
  144.         int v;
  145.         cin >> v;
  146.         a.join_sets(i, v - 1);
  147.     }
  148.     cout << a.get_content();
  149.  
  150.     return 0;
  151. }
  152.  
  153. //
  154. // 3
  155. //
  156.  
  157. #include <iostream>
  158. #include <vector>
  159.  
  160. using namespace std;
  161.  
  162.  
  163. vector<int> color;
  164. vector<vector<int>> polkovnik;
  165. vector<int> rota;
  166.  
  167. void dfs(int v, int parent){
  168.     color[v] = 1;
  169.     for (auto &i : polkovnik[v]){
  170.         if (color[i] == 0){
  171.             dfs(i, v);
  172.         }
  173.         if (color[i] == 1){
  174.             cout << "No";
  175.             exit(0);
  176.         }
  177.     }
  178.     rota.push_back(v + 1);
  179.     color[v] = 2;
  180. }
  181.  
  182.  
  183. int main() {
  184.     int n, m;
  185.     cin >> n >> m;
  186.  
  187.     color = vector<int>(n);
  188.     polkovnik = vector<vector<int>>(n);
  189.  
  190.     for (int i = 0; i < m; i++){
  191.         int nije, vyshe;
  192.         cin >> nije >> vyshe;
  193.         polkovnik[nije - 1].emplace_back(vyshe - 1);
  194.     }
  195.  
  196.     for (int i = 0; i < n; i++){
  197.         if (!color[i]){
  198.             dfs(i, -1);
  199.         }
  200.     }
  201.  
  202.     cout << "Yes" << endl;
  203.     for (int i = 0; i < n; i++){
  204.         cout << rota[n - 1 - i] << ' ';
  205.     }
  206.  
  207.     return 0;
  208. }
Add Comment
Please, Sign In to add comment