Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
935 views

in Online Assessments by Expert (133,030 points)
retagged by | 935 views

1 Answer

0 like 0 dislike
Best answer
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
int c = 0; vector<set<int>> k(200005);unordered_map <int,int> g;
void dfs(int node, vector<vector<int>> &adj, vector<bool> &visited) {
    visited[node] = true;int d = node;
    k[c+1].insert(d); g[d] = c + 1 ;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    int pods, n;
    //cout << "Enter number of nodes and edges: ";
    cin >> pods >> n;
    c = 0 ;
    vector<vector<int>> adj(pods + 1); g.clear();
    vector<bool> visited(pods + 1, false);
    for(int i=1;i<=pods;i++){
        k[i].clear();
    }
    //cout << "Enter edges (u v):" << endl;
    for (int i = 1; i <=n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= pods; ++i) {
        if (!visited[i]){
            dfs(i, adj, visited);
            c++;
        }
    }

    //cout << c << endl;
    
    // for (int i = 1; i <= pods; i++) {
    //     cout << "Set " << i << ": ";
    //     for (int x : k[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    
    int q;cin>>q;//reading the count of queries.
    for(int i=1;i<=q;i++){
        
        
        int l,r;
        cin>>l>>r;
        if(l==1){
            int c1 = g[r];
            int u = k[c1].size();
            if(u==0){
                cout<<"-1";
            }else{
                if(k[c1].find(r)==k[c1].end()){
                    auto g1 = k[c1].begin();
                    cout<<(*g1);
                }
                
                else
                
                {
                    cout<<r;
                }
            }
            cout<<"\n";
        }
        
        if(l==2){
            int c1 = g[r];
            if(k[c1].find(r)!=k[c1].end()){
            k[c1].erase(k[c1].find(r));}
            
        }
        
        
    }
    
    
    
    
    

    return 0;
}
by Expert (114,340 points)