Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std;
- const int maxn = 3e5 + 10;
- int graph[maxn], parent[maxn];
- int farthest_from_node[maxn];
- bool is_deleted[maxn];
- int find_root(int x) {
- while(x != parent[x]) {
- parent[x] = parent[parent[x]];
- x = parent[x];
- }
- return x;
- }
- void unite(int x) {
- int y = find_root(graph[x]);
- if(x == y) {
- farthest_from_node[x] = -1;
- }
- parent[x] = y;
- }
- int main(){
- int n;
- cin >> n;
- for(int i = 1; i <= n; i++) {
- cin >> graph[i];
- parent[i] = i;
- is_deleted[i] = false;
- }
- int q;
- cin >> q;
- vector<pair<int, int>> queries(q);
- for(int i = 0; i < q; i++) {
- cin >> queries[i].first >> queries[i].second;
- if(queries[i].first == 2) {
- is_deleted[queries[i].second] = true;
- }
- }
- for(int i = 1; i <= n; i++) {
- if(!is_deleted[i] and graph[i] != 0) {
- unite(i);
- }
- }
- vector<int> res;
- for(int i = q - 1; i >= 0; i--) {
- if(queries[i].first == 1) {
- int root = find_root(queries[i].second);
- if(farthest_from_node[root] == -1) {
- res.push_back(-1);
- }
- else {
- res.push_back(root);
- }
- }
- else {
- unite(queries[i].second);
- }
- }
- reverse(res.begin(), res.end());
- for(int i = 0; i < res.size(); i++) {
- if(res[i] == -1) {
- cout << "CIKLUS\n";
- }
- else {
- cout << res[i] << "\n";
- }
- }
- return 0;
- }
Advertisement