fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node {
  4. 	vector<node*> l; // neighbors in the original graph
  5. 	vector<node*> c; // children in the CT
  6. 	int a, id; // a is the value of the node, id is its index
  7. 	bool v = false; // initially, no node is marked
  8. };
  9. // <DSU>
  10. int f(int i, int r[]){ // find representant of i
  11. 	if(r[i] == i) return i;
  12. 	return r[i] = f(r[i], r);
  13. }
  14. void merge(int a, int b, int r[], int s[]){
  15. 	a = f(a, r);
  16. 	b = f(b, r);
  17. 	if(a == b) return;
  18. 	if(s[a] > s[b]){
  19. 		r[b] = a;
  20. 		s[a] += s[b];
  21. 	} else {
  22. 		r[a] = b;
  23. 		s[b] += s[a];
  24. 	}
  25. }
  26. // </DSU>
  27. void solve(){
  28. 	// <boring setup>
  29. 	int n,u,v,m;
  30. 	cin >> n >> m;
  31. 	node g[n+1];
  32. 	int o[n], r[n+1], s[n+1];
  33. 	node* c[n+1]; // c[u] is the node with maximum value that u is connected to in the DSU, if u is its own representant
  34. 	for(int i = 1;i <= n;i++) {
  35. 		cin >> g[i].a;
  36. 		g[i].id = i;
  37. 		r[i] = i;
  38. 		s[i] = 1;
  39. 		c[i] = &g[i];
  40. 		o[i-1] = i;
  41. 	}
  42. 	while(m--){
  43. 		cin >> u >> v;
  44. 		g[u].l.push_back(&g[v]);
  45. 		g[v].l.push_back(&g[u]);
  46. 	}
  47. 	// </boring setup>
  48. 	sort(o, o+n, [&g](int a, int b){return g[a].a < g[b].a;}); // sorting the nodes by value
  49. 	for(int j = 0;j < n;j++){
  50. 		node* d = &g[o[j]]; // d is the current node
  51. 		d->v = true; // mark the current node
  52. 		for(node* x : d->l){ // iterate over the neighbors of d
  53. 			if(!x->v || f(x->id, r) == f(d->id, r)) continue; // x is unmarked or it's already connected to d
  54. 			d->c.push_back(c[f(x->id, r)]); // add and edge in the CT between d and the node with maximum value that is connected to x
  55. 			merge(x->id, d->id, r, s); // connect d and x in the DSU
  56. 			c[f(d->id, r)] = d;
  57. 		}
  58. 	}
  59. 	// Use the CT
  60. }
  61. int main(){
  62. 	ios_base::sync_with_stdio(false);
  63. 	cin.tie(0);
  64. 	solve();
  65. }
Runtime error #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/y0cg9M
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!