Sunjaree

DFS

Oct 26th, 2020
899
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using  namespace  std;
  3.  
  4. #define endl     "\n"
  5. #define ll       long long
  6. #define PI       acos(-1.0)
  7. #define test     cout<<"\n****\n"
  8. #define LCM(a,b) ((a/__gcd(a,b))*b)
  9. #define READ(f)  freopen(f, "r", stdin)
  10. #define WRITE(f) freopen(f, "w", stdout)
  11. #define precise  fixed(cout);cout<<setprecision(20)
  12. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  13.  
  14. const int N = 1000;
  15. vector <int> graph[N];
  16. bool visited[N];
  17.  
  18. void DFS(int root){
  19.  
  20.     visited[root] = true;
  21.     cout<<endl<<"Node: "<<root<<endl;
  22.  
  23.     for(int i=0;i<graph[root].size();i++){
  24.         int child = graph[root][i];
  25.         cout<<"Child: "<<child<<", Is visited?-> "<<visited[child]<<endl;
  26.  
  27.         if(!visited[child]){
  28.             cout<<"Entering node-> "<<child<<endl;
  29.             DFS(child);
  30.         }
  31.     }
  32.  
  33.     cout<<"Finished: "<<root<<endl;
  34. }
  35. int main(){
  36.  
  37.     int numNode,numEdge;
  38.     cin>>numNode>>numEdge;
  39.  
  40.     for(int i=0;i<numEdge;i++){
  41.  
  42.         int node,edge;
  43.         cin>>node>>edge;
  44.         graph[node].push_back(edge);
  45.         graph[edge].push_back(node);
  46.     }
  47.     int root;
  48.     cin>>root;
  49.     memset(visited, false,sizeof(visited));
  50.     DFS(root);
  51.  
  52.     return 0;
  53. }
  54.  
  55.  
RAW Paste Data