fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 4e5 + 3;
  5. int par[N];
  6. int r[N];
  7.  
  8. int find(int u) {
  9. if (par[u] == u) return u;
  10. return par[u] = find(par[u]);
  11. }
  12.  
  13. void unite(int u, int v) {
  14. if (par[u] == par[v]) return;
  15. int u_p = find(u);
  16. int v_p = find(v);
  17. if (r[u_p] > r[v_p]) {
  18. par[v_p] = u_p;
  19. r[u_p]++;
  20. } else {
  21. par[u_p] = v_p;
  22. r[v_p]++;
  23. }
  24. }
  25.  
  26. void solve() {
  27. int n;
  28. cin >> n;
  29. vector<int> row1(n + 1), row2(n + 1);
  30. for (int i = 1; i <= n; i++) cin >> row1[i];
  31. for (int i = 1; i <= n; i++) cin >> row2[i];
  32.  
  33. memset(r, 0, (n + 1) * 4);
  34. for (int i = 1; i <= n; i++) par[i] = i;
  35.  
  36. for (int i = 1; i <= n; i++) {
  37. unite(row1[i], row2[i]);
  38. }
  39.  
  40. unordered_set<int> seen;
  41. for (int i = 1; i <= n; i++) {
  42. int p = find(row1[i]);
  43. if (seen.find(p) == seen.end()) {
  44. seen.insert(p);
  45. }
  46. }
  47.  
  48.  
  49. int sz = seen.size();
  50. cout << (1 << sz) << endl;
  51. }
  52.  
  53. int main() {
  54. int t;
  55. cin >> t;
  56. while (t--) solve();
  57. }
Success #stdin #stdout 0s 5588KB
stdin
2
4
1 4 2 3
3 2 1 4
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6
stdout
2
8