fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int parent[1004], ranks[1004];
  5. int T, N;
  6. int cnt;
  7.  
  8. int Find(int x) {
  9. 	if (x == parent[x]) {
  10. 		return x;
  11. 	}
  12. 	else {
  13. 		int y = Find(parent[x]);
  14. 		parent[x] = y;
  15. 		return y;
  16. 	}
  17. }
  18.  
  19. void Union(int x, int y) {
  20. 	x = Find(x);
  21. 	y = Find(y);
  22. 	if (ranks[x] == 0 && ranks[y] == 0)
  23. 		cnt++;
  24.  
  25. 	if (ranks[x] > ranks[y])
  26. 		parent[y] = x;
  27. 	else {
  28. 		parent[x] = y;
  29. 		if (ranks[x] == ranks[y])
  30. 			ranks[y]++;
  31. 	}
  32. }
  33.  
  34. int main() {
  35.  
  36. 	scanf("%d", &T);
  37. 	int num;
  38. 	while (T--) {
  39. 		scanf("%d", &N);
  40. 		cnt = 0;
  41. 		for (int i = 0; i <= N; i++) {
  42. 			parent[i] = i;
  43. 			ranks[i] = 0;
  44. 		}
  45. 		for (int i = 1; i <= N; i++) {
  46. 			scanf("%d", &num);
  47. 			Union(i, num);
  48. 		}
  49. 		printf("%d\n", cnt);
  50. 	}
  51. 	return 0;
  52. }
  53.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
4
3 4 2 1
stdout
copy 
2
https://ideone.com/EJkzz4
language:
C++14 (gcc 8.3)
created:
4 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!