fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int g[100005], cnt[100005];
  4. int mod[100005];
  5. struct dsu{
  6. 	vector<int>par, r;
  7. 	vector<map<int, int>> c;
  8. 	dsu(int n): c(n), par(n), r(n) {};
  9. 	void ms(int v){
  10. 		c[v][g[v]]++;
  11. 		par[v] = v;
  12. 		r[v] = 0;
  13. 	}
  14. 	int fs(int v){
  15. 		return v == par[v] ? v: par[v] = fs(par[v]);
  16. 	}
  17.  
  18. 	void us(int a, int b, int i){
  19. 		int x = a, y = b;
  20. 		a = fs(a);
  21. 		b = fs(b);
  22. 		if (a != b){
  23. 			if(r[a] < r[b]) swap(a, b);
  24. 			par[b] = a;
  25. 			if(r[a] == r[b]) r[a]++;
  26. 			for(auto p: c[b]) c[a][p.first] += p.second;
  27. 			c[b].clear();
  28. 			for(auto p: c[a]){
  29. 				if(mod[p.first] == -1 && c[a][p.first] == cnt[p.first]) mod[p.first] = i;
  30. 			}
  31. 		}
  32. 	}
  33. };
  34.  
  35.  
  36.  
  37. int main() {
  38. 	ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40. 	int n, q, m;
  41. 	cin >> n >> m >> q;
  42. 	dsu qq(n + 1);
  43. 	memset(cnt, 0, sizeof cnt);
  44. 	for(int i = 0; i < n; i++){
  45. 		cin >> g[i + 1];
  46. 		cnt[g[i + 1]]++;
  47. 		qq.ms(i + 1);
  48. 	}
  49. 	for(int i = 1; i <= m; i++){
  50. 		mod[i] = -1;
  51. 	}
  52. 	for(int i = 1; i <= n; i++){
  53. 		if(cnt[g[i]] == 1) mod[g[i]] = 0;
  54. 	}
  55. 	for(int i = 0; i < q; i++){
  56. 		int t, u, v;
  57. 		cin >> u >> v;
  58. 		qq.us(u, v, i + 1);
  59. 	}
  60. 	for(int i = 1; i <= m; i++) cout << mod[i]<< "\n";
  61. 	return 0;
  62. }
  63.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
5 3 4
1 2 3 2 1
1 2
2 3
1 5
4 5
stdout 
3
4
0
https://ideone.com/ZXYPGW
language:
C++14 (clang 8.0)
created:
16 hours 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!