fork download
copy 
  1. #include<bits/stdc++.h>
  2. 		using namespace std;
  3. 		class Tree{
  4. 			int N;
  5. 			list<int> *adj;
  6. 			int *dist;
  7. 			int prevdis;
  8. 			public:
  9.  
  10. 			Tree(int n){
  11. 				this->N = n;
  12. 				adj = new list<int>[N+1];
  13. 				dist = new int[N+1];
  14. 				memset(dist,-1,sizeof(dist));
  15. 				prevdis = 0;
  16. 			}
  17.  
  18. 			void AddEdge(int u,int v){
  19. 				adj[u].push_back(v);
  20. 				adj[v].push_back(u);
  21. 			}
  22.  
  23. 			pair<int,int> DFS(int dist[],int u){
  24. 				dist[u]=prevdis;
  25. 				for(auto it=adj[u].begin();it!=adj[u].end();it++){
  26. 					int t = *it;
  27. 					if(dist[t]==-1){
  28. 						dist[t] = dist[u]+1;
  29. 						prevdis = dist[t];
  30. 						DFS(dist,t);
  31. 					}
  32. 				}
  33.  
  34. 				int max_IND,max_dist=0;
  35. 				for(int i=1;i<=N;i++){
  36. 					if(dist[i]>max_dist){
  37. 						max_dist = dist[i];
  38. 						max_IND = i;
  39. 					}
  40. 				}
  41.  
  42. 				return make_pair(max_IND,max_dist);
  43. 			}
  44.  
  45.  
  46. 			void path(){
  47.  
  48. 				pair<int,int>t1,t2;
  49. 				t1 = DFS(dist,1);
  50. 				memset(dist,-1,sizeof(dist));
  51. 				prevdis = 0;
  52. 				t2 = DFS(dist,t1.first);
  53. 				cout<<t2.second<<"\n";
  54. 			}
  55. 		};
  56.  
  57.  
  58. 		int main(){
  59. 			int t;
  60. 			cin>>t;
  61. 			Tree T(t);
  62. 			int u,v;
  63. 			for(int i=1;i<t;i++){
  64. 				cin>>u>>v;
  65. 				T.AddEdge(u,v);
  66. 			}
  67. 			T.path();
  68. 			   return 0;
  69. 		}       
  70.  
  71.  
  72.  
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
1 2
2 3
3 4
stdout
copy 
Standard output is empty
https://ideone.com/4Yy3li
language:
C++14 (gcc 8.3)
created:
5 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!