fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int parent[100001];
  5. long long sum[100001];
  6. int freq[100001];
  7. vector<vector<int>> v;
  8.  
  9. int find(int x)
  10. {
  11. 	if(x==parent[x])	return x;
  12. 	x=find(parent[x]);
  13. 	return x;
  14. }
  15.  
  16. void add(int a, int b)
  17. {
  18. 	int x=find(a),y=find(b);
  19. 	if(x==y)	return;
  20.  
  21. 	vector<int> tv;
  22. 	for(int temp=0;temp<v[x].size();temp++)
  23. 	{
  24. 		if(v[x][temp] != a)	tv.push_back(v[x][temp]);
  25. 	}
  26. 	v[x].swap(tv);
  27. 	if(v[x].size()!=0)
  28. 	{
  29. 		int leader=v[x][0];
  30. 		freq[leader]=sum[leader]=0;
  31. 		for(int temp=0;temp<v[x].size();temp++)
  32. 		{
  33. 			int node=v[x][temp];
  34. 			parent[node]=leader;
  35. 			freq[leader]++;
  36. 			sum[leader]+=(long long) node;
  37. 		}
  38. 		if(leader!=x)
  39. 		{
  40. 			swap(v[x],v[leader]);
  41. 			v[x].clear();
  42. 		}
  43. 	}
  44. 	freq[y]++;
  45. 	sum[y]+=(long long) a;
  46. 	v[y].push_back(a);
  47. 	parent[a]=y;
  48. }
  49.  
  50. void unite(int a, int b)
  51. {
  52. 	int x=find(a),y=find(b);
  53. 	if(x==y)	return;
  54.  
  55. 	if(freq[y]>freq[x])	swap(x,y);
  56.  
  57. 	freq[x]+=freq[y];
  58. 	sum[x]+=sum[y];
  59.  
  60. 	while(v[y].size()!=0)
  61. 	{
  62. 		int temp=v[y].back();
  63. 		v[y].pop_back();
  64. 		v[x].push_back(temp);
  65. 	}
  66. 	parent[y]=x;
  67. }
  68.  
  69. int main()
  70. {
  71. 	int m,n,temp;
  72. 	while(scanf("%d",&m)!=EOF)
  73. 	{
  74. 		scanf("%d",&n);
  75. 		v.clear();
  76. 		for(temp=1;temp<=m;temp++)
  77. 		{
  78. 			parent[temp]=temp;
  79. 			sum[temp]=temp;
  80. 			freq[temp]=1;
  81. 			vector<int> t;
  82. 			t.push_back(temp);
  83. 			v.push_back(t);
  84. 		}
  85. 		for(temp=0;temp<n;temp++)
  86. 		{
  87. 			int key;
  88. 			scanf("%d",&key);
  89. 			int a,b;
  90. 			if(key==1)
  91. 			{
  92. 				scanf("%d %d",&a,&b);
  93. 				unite(a,b);
  94. 			}
  95. 			if(key==2)
  96. 			{
  97. 				scanf("%d %d",&a,&b);
  98. 				add(a,b);
  99. 			}
  100. 			if(key==3)
  101. 			{
  102. 				scanf("%d",&a);
  103. 				int x=find(a);
  104.  
  105. 				printf("%d %lld\n",freq[x],sum[x]);
  106. 			}
  107. 		}
  108. 	}
  109. }
Success #stdin #stdout 0s 4980KB
comments (?)
stdin
copy 
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
stdout
copy 
3 12
3 7
1 3
3 12
3 7
1 3
https://ideone.com/vZVvCn
language:
C++14 (gcc 8.3)
created:
8 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!