fork download
copy 
  1. //Saturday 25-September-2021 00:11:13
  2. #include <bits/stdc++.h>
  3. //@ReetuRaj77
  4. #define int long long int
  5. #define ulli unsigned long long int
  6.  
  7. #define all(x) (x).begin(),(x).end()
  8.  
  9. #define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr)
  10.  
  11. using namespace std;
  12.  
  13. vector<int>component;
  14. vector<bool>used;
  15. stack<int>order;
  16.  
  17. void dfs1(int source, vector<int>adj[]) {
  18. 	used[source] = true;
  19. 	for (auto v : adj[source]) {
  20. 		if (used[v] == false)
  21. 			dfs1(v, adj);
  22. 	}
  23. 	order.push(source);
  24. }
  25. void dfs2(int source, vector<int>adj_rev[]) {
  26. 	used[source] = true;
  27. 	component.push_back(source);
  28. 	for (auto v : adj_rev[source])
  29. 		if (!used[v])
  30. 			dfs2(v, adj_rev);
  31. }
  32. signed main() {
  33. 	fastio;
  34. 	int n, m;
  35. 	cin >> n >> m;
  36. 	vector<int>values(n);
  37. 	for (auto&x : values)cin >> x;
  38. 	used.resize(n + 1, false);
  39. 	vector<int>adj[n + 1], adj_rev[n + 1];
  40. 	for (int i = 0; i < m; i++) {
  41. 		int x, y;
  42. 		cin >> x >> y;
  43. 		adj[x].push_back(y);
  44. 		adj_rev[y].push_back(x);
  45. 	}
  46. 	for (int i = 1; i < n + 1; i++) {
  47. 		if (used[i] == false) {
  48. 			dfs1(i, adj);
  49. 		}
  50. 	}
  51. 	used.assign(n + 1, false);
  52. 	vector<int>roots(n + 1), root_nodes;
  53. 	vector<int>sums(n + 1);
  54. 	while (!order.empty()) {
  55. 		int i = order.top();
  56. 		order.pop();
  57. 		if (!used[i]) {
  58. 			dfs2(i, adj_rev);
  59. 			int root = component.front();
  60. 			int sum = 0;
  61. 			for (auto u : component) {
  62. 				roots[u] = root;
  63. 				sum += values[u - 1];
  64. 			}
  65. 			sums[root] = sum;
  66. 			root_nodes.push_back(root);
  67. 		}
  68. 		component.clear();
  69. 	}
  70. 	//adjacency matrix of condensation graph.
  71. 	vector<int>adj_scc[n + 1];
  72. 	for (int i = 1; i < n + 1; i++) {
  73. 		for (auto x : adj[i]) {
  74. 			int root_source = roots[i];
  75. 			int root_destination = roots[x];
  76. 			if (root_destination != root_source)
  77. 				adj_scc[root_source].push_back(root_destination);
  78. 		}
  79. 	}
  80. 	reverse(all(root_nodes));
  81. 	for (auto x : root_nodes) {
  82. 		int val = sums[x];
  83. 		for (auto v : adj_scc[x]) {
  84. 			val = max(val, sums[x] + sums[v]);
  85. 		}
  86. 		sums[x] = val;
  87. 	}
  88. 	cout << *max_element(all(sums)) << endl;
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 5424KB
comments (?)
stdin
copy 
10 20
2 2 6 3 1 5 9 8 7 4
10 4
2 8
9 8
10 8
9 6
1 10
10 2
4 7
10 6
6 8
9 10
8 9
8 1
4 8
7 10
2 5
10 9
7 5
3 6
1 8
stdout
copy 
47
https://ideone.com/qTH34t
language:
C++14 (gcc 8.3)
created:
2 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!