fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define endl "\n"
  6. #define long long long 
  7.  
  8. class Graph{
  9. 	long int v;
  10. 	list<long int> *adj;
  11.  
  12. 	public:
  13. 		Graph(long int v) : v(v){
  14. 			adj = new list<long int>[v];
  15. 		}
  16.  
  17. 		void addEdge(long int u, long int v){
  18. 			adj[u].push_back(v);
  19. 			adj[v].push_back(u);
  20. 		}
  21.  
  22. 		long int findLastVertex(){
  23. 			vector<long int> distance(v,LONG_MAX);
  24. 			queue<long int> q;
  25. 			distance[0] = 0;
  26. 			q.push(0);
  27.  
  28. 			while(!q.empty()){
  29. 				auto ele = q.front();
  30. 				q.pop();
  31.  
  32. 				for(auto e : adj[ele]){
  33. 					if(distance[e] == LONG_MAX){
  34. 						distance[e] = distance[ele] + 1;
  35. 						q.push(e);
  36. 					}
  37. 				}
  38. 			}
  39. 			// for(auto ele : distance)
  40. 			// 	cout<<ele<<" ";
  41. 			// cout<<endl;
  42. 			return max_element(distance.begin(),distance.end()) - distance.begin();
  43. 		}
  44.  
  45. 		long int findDiameter(long int lastVertex){
  46. 			vector<long int> distance(v,LONG_MAX);
  47. 			queue<long int> q;
  48. 			distance[lastVertex] = 0;
  49. 			q.push(lastVertex);
  50.  
  51. 			while(!q.empty()){
  52. 				auto ele = q.front();
  53. 				q.pop();
  54.  
  55. 				for(auto e : adj[ele]){
  56. 					if(distance[e] == LONG_MAX){
  57. 						distance[e] = distance[ele] + 1;
  58. 						q.push(e);
  59. 					}
  60. 				}
  61. 			}
  62. 			return *max_element(distance.begin(),distance.end());
  63. 		}
  64. };
  65.  
  66. int main(){
  67.    IOS;
  68.  
  69.    long int n;
  70.    cin>>n;
  71.  
  72.    long int ans = 0;
  73.  
  74.    while(n--){
  75.    	long int v;
  76.    	cin>>v;
  77.    	Graph g(v);
  78.  
  79.    	for(long int i = 0; i < v-1; i++){
  80.    		long int a,b;
  81.    		cin>>a>>b;
  82.    		g.addEdge(a-1,b-1);
  83.    	}
  84.    	// cout<<ans<<endl;
  85.    	ans += g.findDiameter(g.findLastVertex());
  86.    }
  87.    cout<<ans;
  88.    return 0;
  89. }
Success #stdin #stdout 0s 4300KB
comments (?)
stdin
copy 
1

3 1 2 2 3
stdout
copy 
2
https://ideone.com/HiOD03
language:
C++14 (gcc 8.3)
created:
4 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!