fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int depth = 0;
  6. void dfs(int node, vector<vector<int>> &graph, vector<int> & depthOf, int & leaf){
  7.     for(int child : graph[node])
  8.         if(!depthOf[child]){
  9.  
  10.             depthOf[child] = ++depth;
  11.  
  12.             if(depthOf[leaf] < depthOf[child])
  13.                 leaf = child;
  14.  
  15.             dfs(child, graph, depthOf, leaf);
  16.             depth--;
  17.         }
  18. }
  19. int main(){
  20.  
  21.     int nodes, edges, firstLeaf = 0, secondLeaf = 0;
  22.     cin >> nodes >> edges;
  23.  
  24.     vector<vector<int>> graph(nodes + 1);
  25.     vector<int> depthOf(nodes + 1), beZero(nodes + 1),
  26.                 path(nodes + 1);
  27.  
  28.     while(edges--){
  29.         int from, to;
  30.         cin >> from >> to;
  31.  
  32.         graph[from].push_back(to);
  33.         graph[to].push_back(from);
  34.     }
  35.  
  36.     // to get firstLeaf
  37.  
  38.     int node = 1; // root
  39.  
  40.     if(!depthOf[node]){
  41.  
  42.         depthOf[node] = ++depth;
  43.  
  44.         if(depthOf[firstLeaf] < depthOf[node])
  45.             firstLeaf = node;
  46.  
  47.         dfs(node, graph, depthOf, firstLeaf);
  48.     }
  49.  
  50.     // to get SecondLeaf
  51.  
  52.     node = firstLeaf; // firstLeaf
  53.     depthOf = beZero;
  54.     depth = 0;
  55.  
  56.     if(!depthOf[node]){
  57.  
  58.         depthOf[node] = ++depth;
  59.         if(depthOf[secondLeaf] < depthOf[node])
  60.             secondLeaf = node;
  61.  
  62.         dfs(node, graph, depthOf, secondLeaf);
  63.     }
  64.  
  65.  
  66.     cout << endl;
  67.     cout <<"First  Leaf  = "<< firstLeaf << endl;
  68.     cout <<"Second Leaf  = "<< secondLeaf << endl;
  69.     cout <<"Longest Path (edges) = "<< depthOf[secondLeaf] - 1 << endl;
  70. 	cout <<"Longest Path (nodes) = "<< depthOf[secondLeaf] << endl;
  71. }
  72.  
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
8 7
1 2
2 4
1 3
3 7
3 5
3 6
6 8
stdout
copy 
First  Leaf  = 8
Second Leaf  = 4
Longest Path (edges) = 5
Longest Path (nodes) = 6
https://ideone.com/Ell6mN
Longest Path
language:
C++14 (gcc 8.3)
created:
4 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!