Advertisement
Josif_tepe

Untitled

May 23rd, 2023
675
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 3e5 + 10;
  5. int n;
  6. int parent[maxn];
  7. int graph[maxn];
  8. bool is_deleted[maxn];
  9. int furthest_from_node[maxn];
  10. int find_root(int x) {
  11.     while(x != parent[x]) {
  12.         parent[x] = parent[parent[x]];
  13.         x = parent[x];
  14.     }
  15.     return x;
  16. }
  17. void unite(int x) {
  18.     int y = find_root(graph[x]);
  19.     if(x == y) {
  20.         furthest_from_node[x] = -1;
  21.     }
  22.     parent[x] = y;
  23. }
  24. int main(){
  25.     ios_base::sync_with_stdio(false);
  26.     cin >> n;
  27.     for(int i = 1; i <= n; i++) {
  28.         cin >> graph[i];
  29.         parent[i] = i;
  30.         is_deleted[i] = false;
  31.     }
  32.     vector<pair<int, int> > queries;
  33.     int q;
  34.     cin >> q;
  35.    
  36.     for(int i = 0; i < q; i++) {
  37.         int a, b;
  38.         cin >> a >> b;
  39.         if(a == 2) {
  40.             is_deleted[b] = true;
  41.         }
  42.         queries.push_back(make_pair(a, b));
  43.     }
  44.     for(int i = 1; i <= n; i++) {
  45.         if(!is_deleted[i] and graph[i] != 0) {
  46.             unite(i);
  47.         }
  48.     }
  49.     vector<int> ans;
  50.     for(int i = q - 1; i >= 0; i--) {
  51.         if(queries[i].first == 1) {
  52.             int root = find_root(queries[i].second);
  53.             if(furthest_from_node[root] == -1) {
  54.                 ans.push_back(-1);
  55.             }
  56.             else {
  57.                 ans.push_back(root);
  58.             }
  59.         }
  60.         else {
  61.             unite(queries[i].second);
  62.         }
  63.     }
  64.    
  65.     for(int i = (int) ans.size() - 1; i >= 0; i--) {
  66.         if(ans[i] == -1) {
  67.             cout << "CIKLUS\n";
  68.         }
  69.         else {
  70.             cout << ans[i] << "\n";
  71.         }
  72.     }
  73.     return 0;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement