Advertisement
Guest User

Task

a guest
Jan 27th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. const int MAX_SIZE = 100;
  2.  
  3. bool used[MAX_SIZE] = {false,};
  4.  
  5. bool hasPath(vector<vector<int>> graph, int a, int b){
  6.     if(a == b){
  7.        // cout<<a<<"=="<<b<<endl;
  8.         return true;
  9.     }
  10.     else{
  11.         used[a] = true;
  12.         cout<<"used["<<a<<"]="<<1<<endl;
  13.         cout<<"size: "<<graph[a].size()<<endl;
  14.         for(unsigned i = 0; i<graph[a].size(); i++){
  15.             if(used[graph[a][i]] == 0){
  16.                 //cout<<graph[a][i]<<" ->"<<b<<endl;
  17.                 // used[graph[a][i]] = true;
  18.                 used[graph[a][i]] = true;
  19.                 return hasPath(graph, graph[a][i], b);
  20.                 used[graph[a][i]] = true;
  21.  
  22.             }
  23.         }
  24.         // used[a] = true;
  25.     }
  26.     return false;
  27. }
  28.  
  29. int main()
  30. {
  31.     int n = 10;
  32.     vector<vector<int>> graph(n);
  33.  
  34.     int m = 5;
  35.     for(int i = 0; i<m; i++){
  36.         int first, second;
  37.         cin>>first>>second;
  38.         graph[first].push_back(second);
  39.         graph[second].push_back(first);
  40.     }
  41.  
  42.     for(int i =0; i<10; i++){
  43.         cout<<i<<" : ";
  44.         for(int j = 0; j<graph[i].size(); j++){
  45.             cout<<graph[i][j]<<" ";
  46.         }
  47.         cout<<endl;
  48.     }
  49.  
  50.     int a = 1, b = 5;
  51.     cout<<"Has path between 1 and 5 : "<<hasPath(graph,a,b)<<endl;
  52.  
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement