Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int maxn = 3e5 + 10;
- int n;
- int parent[maxn];
- int graph[maxn];
- bool is_deleted[maxn];
- int furthest_from_node[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) {
- furthest_from_node[x] = -1;
- }
- parent[x] = y;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin >> n;
- for(int i = 1; i <= n; i++) {
- cin >> graph[i];
- parent[i] = i;
- is_deleted[i] = false;
- }
- vector<pair<int, int> > queries;
- int q;
- cin >> q;
- for(int i = 0; i < q; i++) {
- int a, b;
- cin >> a >> b;
- if(a == 2) {
- is_deleted[b] = true;
- }
- queries.push_back(make_pair(a, b));
- }
- for(int i = 1; i <= n; i++) {
- if(!is_deleted[i] and graph[i] != 0) {
- unite(i);
- }
- }
- vector<int> ans;
- for(int i = q - 1; i >= 0; i--) {
- if(queries[i].first == 1) {
- int root = find_root(queries[i].second);
- if(furthest_from_node[root] == -1) {
- ans.push_back(-1);
- }
- else {
- ans.push_back(root);
- }
- }
- else {
- unite(queries[i].second);
- }
- }
- for(int i = (int) ans.size() - 1; i >= 0; i--) {
- if(ans[i] == -1) {
- cout << "CIKLUS\n";
- }
- else {
- cout << ans[i] << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement