fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int componentCnt = 0;
  7.  
  8. // component[node] = component number of node
  9. vector<int> component;
  10.  
  11. // stores all alive nodes of each component
  12. vector<set<int>> compSet;
  13.  
  14. void dfs(int node,
  15.          vector<vector<int>> &adj,
  16.          vector<bool> &vis)
  17. {
  18.     vis[node] = true;
  19.  
  20.     component[node] = componentCnt;
  21.     compSet[componentCnt].insert(node);
  22.  
  23.     for (int child : adj[node])
  24.     {
  25.         if (!vis[child])
  26.             dfs(child, adj, vis);
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(nullptr);
  34.  
  35.     int pods, edges;
  36.     cin >> pods >> edges;
  37.  
  38.     vector<vector<int>> adj(pods + 1);
  39.  
  40.     for (int i = 0; i < edges; i++)
  41.     {
  42.         int u, v;
  43.         cin >> u >> v;
  44.  
  45.         adj[u].push_back(v);
  46.         adj[v].push_back(u);
  47.     }
  48.  
  49.     component.assign(pods + 1, 0);
  50.     compSet.resize(pods + 1);
  51.  
  52.     vector<bool> vis(pods + 1, false);
  53.  
  54.     // Find connected components
  55.     for (int i = 1; i <= pods; i++)
  56.     {
  57.         if (!vis[i])
  58.         {
  59.             componentCnt++;
  60.             dfs(i, adj, vis);
  61.         }
  62.     }
  63.  
  64.     int q;
  65.     cin >> q;
  66.  
  67.     while (q--)
  68.     {
  69.         int type, x;
  70.         cin >> type >> x;
  71.  
  72.         int id = component[x];
  73.  
  74.         if (type == 1)
  75.         {
  76.             if (compSet[id].empty())
  77.             {
  78.                 cout << -1 << "\n";
  79.             }
  80.             else if (compSet[id].count(x))
  81.             {
  82.                 cout << x << "\n";
  83.             }
  84.             else
  85.             {
  86.                 cout << *compSet[id].begin() << "\n";
  87.             }
  88.         }
  89.         else
  90.         {
  91.             compSet[id].erase(x);
  92.         }
  93.     }
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5 3
1 2
2 3
4 5
6
1 1
2 1
1 1
1 2
2 2
1 2
stdout
copy 
1
2
2
3
https://ideone.com/6J4pGP
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!