fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <queue>
  4. #include <memory.h>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 500000;
  9. int n, m;
  10. int L[N], Z[N], maxLen[N];
  11. vector<vector<pair<int, int> > > g;
  12. bool isBridge[2 * N];
  13. int low[N], idx[N], dfs;
  14. bool vis[N];
  15. int parent[N];
  16. void markBridges(int u, int p) {
  17. 	low[u] = idx[u] = ++dfs;
  18. 	for (int i = 0; i < g[u].size(); ++i) {
  19. 		int v = g[u][i].first;
  20. 		if (idx[v] == 0) {
  21. 			markBridges(v, u);
  22. 			low[u] = min(low[u], low[v]);
  23. 			if (low[v] > idx[u])
  24. 				isBridge[g[u][i].second] = true;
  25. 		}
  26. 		else if (v != p)
  27. 			low[u] = min(low[u], idx[v]);
  28. 	}
  29. }
  30. void findASpanningTreeAndInitializeL(int startingNode) {
  31. 	queue<int> q;
  32. 	vector<int> nodesByDepth;
  33. 	q.push(startingNode);
  34. 	memset(vis, 0, sizeof(vis));
  35. 	vis[startingNode] = true;
  36. 	parent[startingNode] = -1;
  37. 	while (!q.empty()) {
  38. 		int u = q.front();
  39. 		q.pop();
  40. 		nodesByDepth.push_back(u);
  41. 		for (auto e : g[u]) {
  42. 			int v = e.first;
  43. 			if (vis[v])
  44. 				continue;
  45. 			vis[v] = true;
  46. 			parent[v] = u;
  47. 			q.push(v);
  48. 		}
  49. 	}
  50. 	for (int i = n - 1; i >= 0; --i) {
  51. 		int u = nodesByDepth[i];
  52. 		for (auto e : g[u]) {
  53. 			int v = e.first;
  54. 			if (parent[v] == u) {
  55. 				maxLen[u] = max(maxLen[u], 1 + maxLen[v]);
  56. 				if (isBridge[e.second])
  57. 					L[u] = max(L[u], 1 + maxLen[v]);
  58. 			}
  59. 		}
  60. 	}
  61. }
  62. vector<vector<int> > cycles; // actually components after removing bridges, not cycles (as there can be a single node).
  63. int cycleIdx[N];
  64. void findCycles(int u) {
  65. 	vis[u] = true;
  66. 	cycles.back().push_back(u);
  67. 	cycleIdx[u] = cycles.size() - 1;
  68. 	for (auto e : g[u])
  69. 		if (!isBridge[e.second] && !vis[e.first])
  70. 			findCycles(e.first);
  71. }
  72. void solveCycles(int u, int p, int upValue) {
  73. 	L[u] = max(L[u], upValue);
  74. 	vector<int> &cycle = cycles[cycleIdx[u]];
  75. 	int k = cycle.size();
  76. 	for (int it = 0; it < 2; ++it) { // two iterations, clockwise and counter clockwise
  77. 		priority_queue<pair<int, int> > q;
  78. 		for (int i = 0; i < 2 * k; ++i) {
  79. 			int d = 2 * k - i;
  80. 			while (!q.empty() && q.top().second - d > k / 2)
  81. 				q.pop();
  82. 			if (!q.empty())
  83. 				Z[cycle[i%k]] = max(Z[cycle[i%k]], q.top().first - d);
  84. 			q.push({ L[cycle[i%k]] + d,d });
  85. 		}
  86. 		reverse(cycle.begin(), cycle.end());
  87. 	}
  88. 	for (auto u : cycle) {
  89. 		int firstMax = 0, secondMax = 0;
  90. 		for (auto e : g[u])
  91. 			if (e.first != p && isBridge[e.second]) {
  92. 				int v = e.first;
  93. 				if (secondMax < 1 + maxLen[v]) {
  94. 					secondMax = 1 + maxLen[v];
  95. 					if (firstMax < secondMax)
  96. 						swap(firstMax, secondMax);
  97. 				}
  98. 			}
  99. 		for (auto e : g[u])
  100. 			if (e.first != p && isBridge[e.second]) {
  101. 				int v = e.first;
  102. 				int passValue = max(upValue, Z[u]);
  103. 				if (firstMax == 1 + maxLen[v])
  104. 					passValue = max(passValue, secondMax);
  105. 				else
  106. 					passValue = max(passValue, firstMax);
  107. 				solveCycles(v, u, passValue + 1);
  108. 			}
  109. 	}
  110. }
  111. int main()
  112. {
  113. 	scanf("%d%d", &n, &m);
  114. 	g.resize(n);
  115. 	for (int i = 0, u, v; i < m; ++i) {
  116. 		scanf("%d%d", &u, &v);
  117. 		--u; --v;
  118. 		g[u].push_back({ v,i });
  119. 		g[v].push_back({ u,i });
  120. 	}
  121. 	markBridges(0, -1);
  122. 	for (int i = 0; i < n; ++i)
  123. 		if (!vis[i]) {
  124. 			cycles.push_back(vector<int>());
  125. 			findCycles(i);
  126. 		}
  127. 	findASpanningTreeAndInitializeL(0);
  128. 	solveCycles(0, -1, 0);
  129. 	for (int i = 0; i < n; ++i) {
  130. 		if (i > 0)
  131. 			printf(" ");
  132. 		printf("%d", max(L[i], Z[i]));
  133. 	}
  134. 	printf("\n");
  135. 	return 0;
  136. }
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
9 10
7 2
9 2
1 6
3 1
4 3
4 7
7 6
9 8
5 8
5 9
stdout
copy 
5 3 5 4 5 4 3 5 4
https://ideone.com/EEORpR
language:
C++14 (gcc 8.3)
created:
6 years 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!