fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<iterator>
  4. #include<stdio.h>
  5.  
  6. using namespace std;
  7.  
  8. vector <bool> visited;
  9. vector <int> longest_path;
  10. vector <bool> was;
  11.  
  12. vector < vector<int> > graph;
  13.  
  14. int max_path = 0;
  15.  
  16. void longest_from_node(int v,int path)
  17. {
  18.  
  19. 	if(was[v] == true) return;
  20.  
  21. 	//cout << "LFN in node: "<< v+1 <<endl;
  22. 	path++;
  23. 	longest_path[v] = path;
  24. 	if(path > max_path) max_path = path;
  25.  
  26. 	visited[v] = true;
  27.  
  28. 	for(vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++)
  29.     {
  30.         if( ! visited[*it]) //note that *it repr the adj vert
  31.         {
  32.             longest_from_node(*it,path);
  33.         }
  34.     }
  35.  
  36. }
  37.  
  38. int main()
  39. {
  40.  
  41. 	int NO;
  42. 	int u,v,way = 0,c;
  43. 	scanf("%d",&NO);
  44.  
  45. 	graph = vector< vector<int> > (NO);
  46. 	c = NO-1;
  47. 	while(c--)
  48. 	{
  49. 		scanf("%d %d", &u, &v);
  50. 		u--;
  51. 		v--;
  52.  
  53. 		graph[u].push_back(v);
  54. 		graph[v].push_back(u);
  55. 	}
  56. 	longest_path = vector <int> (NO,0);
  57. 	visited = vector <bool> (NO,0);
  58. 	was = vector<bool> (NO,0);
  59. 	//longest_paths = vector<vector<int>> (NO);
  60. 	//new_longest_path = vector<int> (NO,0);
  61. 	int new_longest_path = 0;
  62. 	for(int i = 0; i < NO; i++)
  63. 	{
  64. 		max_path = 0;
  65. 		visited = vector <bool> (NO,0);
  66. 		int current_longest = 0;
  67. 		int current_2nd_longest = 0;
  68. 		int pom;
  69. 		was[i] = true;
  70. 		for(vector<int>::iterator it = graph[i].begin(); it != graph[i].end(); it++)
  71. 		{		
  72. 				if(was[*it] == true) continue;
  73. 				//cout << "Curret parent: "<< i+1 <<endl;
  74. 				max_path = 0;
  75. 				longest_from_node(*it,-1);
  76.  
  77. 				if(max_path > current_longest)
  78. 				{
  79. 					current_2nd_longest = current_longest;
  80. 					current_longest = max_path;
  81.  
  82.  
  83. 					//cout << "\tNode: "<< (*it + 1) << " new local longest_path = "<<max_path << endl;
  84. 					//cout << "\tso 2nd = " << current_2nd_longest<<endl;
  85. 				}
  86. 				else
  87. 				{
  88. 					if(max_path > current_2nd_longest) current_2nd_longest = max_path;
  89. 					//cout << "\tNode: "<< (*it + 1) << " just new 2nd = " << current_2nd_longest<<endl;
  90. 				}
  91.  
  92. 				if(current_2nd_longest == 0)
  93. 					pom = current_longest + current_2nd_longest  + 1;
  94. 				else
  95. 					pom = current_longest + current_2nd_longest  + 2;					
  96. 				if(pom > new_longest_path)
  97. 				{
  98. 					new_longest_path = pom;
  99. 					//cout << "\tNode: " << i+1 << " gives us new global longest path = " <<new_longest_path<<endl;
  100. 				}
  101.  
  102.  
  103. 		}
  104.  
  105.  
  106. 	}
  107.  
  108. 	printf("%d\n", new_longest_path);
  109.  
  110.  
  111. }
  112.  
Runtime error #stdin #stdout #stderr 0s 3760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/RhhwIC
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!