fork(61) download
copy 
  1. /* 
  2.    Copyright 2013 Jakub "Cubix651" Cisło
  3.    Solving Lowest Common Ancestor (LCA) problem offline.
  4.    Tarjan's algorithm. Complexity: O(alpha(n) * n)
  5. */
  6. #include <cstdio>
  7. #include <vector>
  8. using namespace std;
  9.  
  10. const int MAX = 1000000;
  11. vector<int> graph[MAX], query[MAX], answer[MAX];
  12. int n, q, x, y, rep[MAX], rank[MAX], anc[MAX];
  13. short int visited[MAX]; //0 - not visited, 1 - visited 2 - processed
  14.  
  15. int Find(int a)
  16. {
  17.     if(rep[a] != a)
  18. 		rep[a] = Find(rep[a]);
  19. 	return rep[a];
  20. }
  21.  
  22. void Union(int a, int b)
  23. {
  24. 	a = Find(a);
  25. 	b = Find(b);
  26. 	if(a == b) return;
  27.  
  28. 	if(rank[a] < rank[b])
  29. 		rep[a] = b;
  30. 	else if(rank[b] < rank[a])
  31. 		rep[b] = a;
  32. 	else
  33. 	{
  34. 		rep[a] = b;
  35. 		++rank[b];
  36. 	}
  37. }
  38.  
  39. void MakeSets(int m)
  40. {
  41. 	while(m--)
  42. 	{
  43. 		rep[m] = m;
  44. 		rank[m] = 0;
  45. 	}
  46. }
  47.  
  48. void dfs(int v)
  49. {
  50. 	visited[v] = 1;
  51. 	anc[v] = v;
  52. 	for(int i = 0; i < graph[v].size(); ++i)
  53. 	{
  54. 		if(visited[graph[v][i]] == 0)
  55. 		{
  56. 			dfs(graph[v][i]);
  57. 			Union(v, graph[v][i]);
  58. 			anc[Find(v)] = v;
  59. 		}
  60. 	}
  61. 	visited[v] = 2;
  62. 	for(int i = 0; i < query[v].size(); ++i)
  63. 	{
  64. 		if(visited[query[v][i]] == 2)
  65. 			answer[v][i] = anc[Find(query[v][i])];
  66. 	}
  67. }
  68.  
  69. void LCA(int n, int root)
  70. {
  71. 	MakeSets(n);
  72. 	for(int i = 1; i <= n; ++i)
  73. 		answer[i].resize(query[i].size());
  74. 	dfs(root);
  75. }
  76.  
  77. int main()
  78. {
  79. 	scanf("%d", &n);
  80. 	for(int i = 1; i < n; ++i)
  81. 	{
  82. 		scanf("%d%d", &x, &y);
  83. 		graph[x].push_back(y);
  84. 		graph[y].push_back(x);
  85. 	}
  86. 	scanf("%d", &q);
  87. 	while(q--)
  88. 	{
  89. 		scanf("%d%d", &x, &y);
  90. 		query[x].push_back(y);
  91. 		if(x!=y)
  92. 			query[y].push_back(x);
  93. 	}
  94. 	LCA(n, 1);
  95. 	for(int i = 1; i <= n; ++i)
  96. 	{
  97. 		for(int j = 0; j < query[i].size(); ++j)
  98. 		{
  99. 			if(answer[i][j] != 0)
  100. 				printf("LCA(%d, %d) = %d\n", i, query[i][j], answer[i][j]);
  101. 		}
  102. 	}
  103. 	return 0;
  104. }
Success #stdin #stdout 0.03s 51824KB
comments (?)
stdin
copy 
16
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
5 10
5 11
5 12
6 13
6 14
13 15
13 16
10
1 4
6 11
15 8
9 9
10 12
8 9
13 12
13 15
16 14
12 13
stdout
copy 
LCA(1, 4) = 1
LCA(6, 11) = 2
LCA(8, 15) = 1
LCA(9, 9) = 9
LCA(9, 8) = 4
LCA(12, 10) = 5
LCA(13, 12) = 2
LCA(13, 15) = 13
LCA(13, 12) = 2
LCA(14, 16) = 6
https://ideone.com/Y1OiII
LCA Tarjan
language:
C++ (gcc 8.3)
created:
11 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!