fork(2) download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. const int MX = 1e5 + 5; 
  5. int arr[MX], color[MX], p[MX], r[MX], par[MX];
  6.  
  7. void init(){
  8. 	for(int i = 0; i < MX; i++){
  9. 		color[i] = par[i] = -1;
  10. 		p[i] = i;
  11. 		r[i] = 0;
  12. 	}
  13. }
  14.  
  15. int find_par(int i){
  16. 	return (p[i] == i) ? i :(p[i] = find_par(p[i]));
  17. }
  18.  
  19. void union_set(int i, int j){
  20. 	int x = find_par(i), y = find_par(j);
  21. 	if(x != y){
  22. 		if(r[x] > r[y]){
  23. 			p[y] = x;
  24. 		}else{
  25. 			p[x] = y;
  26. 			if(r[x] == r[y]) r[y]++;
  27. 		}
  28. 	}
  29. }
  30.  
  31. int main() {
  32. 	int t, n, q, id, u, v;
  33. 	scanf("%d", &t);
  34. 	for(int i = 1; i <= t; i++){
  35. 		scanf("%d %d", &n, &q);
  36. 		init();
  37. 		for(int j = 1; j <= n; scanf("%d", &arr[j]), j++);
  38. 		for(int j = 1; j <= n; j++){
  39. 			if(color[arr[j]] == -1){
  40. 				color[arr[j]] = j;
  41. 				par[j] = arr[j];
  42. 			}else{
  43. 				int x = color[arr[j]];
  44. 				union_set(x, j);
  45. 				x = find_par(j);
  46. 				color[arr[j]] = x;
  47. 				par[x] = arr[j];
  48. 			}
  49. 		}
  50.  
  51. 		printf("Case %d:\n", i);
  52. 		for(int j = 1; j <= q; j++){
  53. 			scanf("%d %d", &id, &u);
  54. 			if(id == 1){
  55. 				scanf("%d", &v);
  56. 				if(color[u] != -1){
  57. 					if(color[v] != -1){
  58. 						union_set(color[u], color[v]);
  59. 						int x = find_par(color[u]);
  60. 						color[v] = x;
  61. 						par[x] = v;
  62. 					}else{
  63. 						color[v] = color[u];
  64. 						par[color[u]] = v;
  65. 					}
  66. 					color[u] = -1;
  67. 				}
  68. 			}else{
  69. 				int x = find_par(u);
  70. 				printf("%d\n", par[x]);
  71. 			}
  72. 		}
  73. 	}
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 17184KB
comments (?)
stdin
copy 
1
5 4
1 2 3 4 5
1 1 3
2 1
1 3 5
2 1
stdout
copy 
Case 1:
3
5
https://ideone.com/USMnVT
language:
C++14 (gcc 8.3)
created:
5 years 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!