fork download
copy 
  1. #include <vector>
  2. #include <deque>
  3. #include <list>
  4. #include <algorithm>
  5. #include <map>
  6. #include <iostream>
  7. /*
  8.  *            A
  9.  *          B   C
  10.  *        D  E   F
  11.  *       G
  12.  *
  13.  * meghdar avalie :  (A,B),(A,C)
  14.  * gostraresh (A,B)  (A,C),(A,B,D),(A,B,E)
  15.  *                   (A,B,D),(A,B,E),(A,C,F)
  16.  *                   (A,B,E),(A,C,F),(A,B,D,G)
  17.  *                   (A,C,F),(A,B,D,G)
  18.  *                   (A,B,D,G)
  19.  *                     ...
  20.  */
  21.  
  22. using AdjList=std::vector<std::vector<size_t>>;
  23.  
  24. std::vector<size_t>  findMaxDistance(const AdjList& adjList)
  25. {
  26.     std::deque<std::vector<size_t>> remain_nodes;
  27.  
  28.     //meghdar avalie
  29.     for(size_t i=0;i<adjList[0].size();i++)
  30.     {
  31.         std::vector<size_t> pval;
  32.         pval.push_back(0);
  33.         pval.push_back(adjList[0][i]);
  34.         remain_nodes.push_back(pval);
  35.  
  36.     }
  37.     //
  38.  
  39.     std::vector<size_t> max_dist=remain_nodes[0];//for storing the longest path
  40.  
  41.     while(remain_nodes.size() > 0 )
  42.     {
  43.         int Node=remain_nodes[0][remain_nodes[0].size()-1];//last node  the list
  44.         //expand first pair
  45.         if(Node<adjList.size()){
  46.             for(size_t i=0;i<adjList[Node].size();i++){
  47.                 if(std::find(remain_nodes[0].begin(),
  48.                              remain_nodes[0].end(),adjList[Node][i])==remain_nodes[0].end()){
  49.                     std::vector<size_t> temp=remain_nodes[0];
  50.                     temp.push_back(adjList[Node][i]);
  51.                     remain_nodes.push_back(std::move(temp));
  52.                 }
  53.             }
  54.         }
  55.  
  56.         //if expanded node is bigger than max_dist put it in max_dist
  57.         if(remain_nodes[0].size()>max_dist.size())
  58.             max_dist=remain_nodes[0];
  59.  
  60.         // remove expanded node
  61.         remain_nodes.pop_front();
  62.     }
  63.     return max_dist;
  64. }
  65.  
  66. int main()
  67. {
  68.     //graph shekl bala
  69.     AdjList adjList({ {1,2},
  70.                       {3,4},
  71.                       {5},
  72.                       {6}
  73.                     });
  74.     std::vector<size_t> result=findMaxDistance(adjList);
  75.     std::map<int,std::string> Names;
  76.     Names[0]="A";Names[1]="B";Names[2]="C";
  77.     Names[3]="D";Names[4]="E";Names[5]="F";
  78.     Names[6]="G";
  79.     for(auto i:result){
  80.         std::cout<<Names[i];//result ABDG
  81.     }
  82. }
  83.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ABDG
https://ideone.com/r1EvVl
language:
C++14 (gcc 8.3)
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!