fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. using namespace __gnu_pbds;
  12. template <class T>
  13. using orderStaticTree =
  14.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  15.  
  16. #define ll long long
  17.  
  18. #define saleh                         \
  19.     ios_base::sync_with_stdio(false); \
  20.     cin.tie(nullptr);
  21.  
  22. const int md = 1e9 + 7;
  23. #define ll long long
  24.  
  25. const ll remo = -1e18;
  26.  
  27. long long fastPower(long long base, long long exponent)
  28. {
  29.     long long result = 1;
  30.     while (exponent > 0)
  31.     {
  32.         if (exponent % 2 == 1)
  33.         {
  34.             result = (result * base) % md;
  35.         }
  36.         base = (base * base) % md;
  37.         exponent /= 2;
  38.     }
  39.     return result % md;
  40. }
  41. const int maxi = 1e5 + 100;
  42. vector<int> adj[maxi];
  43. vector<bool> vis(maxi);
  44.  
  45. void dfs(int node)
  46. {
  47.     vis[node] = 1;
  48.     for (int i : adj[node])
  49.     {
  50.         if (!vis[i])
  51.         {
  52.             dfs(i);
  53.         }
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59.     saleh;
  60.     int t;
  61.     cin >> t;
  62.     while (t--)
  63.     {
  64.  
  65.         int n;
  66.         cin >> n;
  67.         for (int i = 1; i <= maxi - 1; i++)
  68.         {
  69.             adj[i].clear();
  70.             vis[i] = 0;
  71.         }
  72.  
  73.         for (int i = 0; i < n; i++)
  74.         {
  75.             int a, b;
  76.             cin >> a >> b;
  77.             adj[a].push_back(b);
  78.             adj[b].push_back(a);
  79.         }
  80.         int ans = 0;
  81.         for (int i = 1; i <= n; i++)
  82.         {
  83.             if (!vis[i])
  84.             {
  85.                 ans++;
  86.                 dfs(i);
  87.             }
  88.         }
  89.  
  90.         ll ansii = fastPower(2, ans)%md - 1;
  91.         cout << ansii%md << endl;
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/LVOMWx
language:
C++ (gcc 8.3)
created:
6 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!