Rakibul_Ahasan

DFS_Implementation

Nov 11th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.   #define WHITE 1
  5.   #define GRAY 2
  6.   #define BLACK 3
  7.  
  8.   int adj[100][100];
  9.   int node,edge;
  10.   int color[100];
  11.  
  12.   int Time=1;
  13.   int Stime[100];
  14.   int Ftime[100];
  15.  
  16.  void dfs_visit(int x)
  17.  {
  18.     color[x]=GRAY;
  19.     Stime[x]=Time;
  20.     ++Time;
  21.     for(int i=0; i<node; i++)
  22.     {
  23.         if(adj[x][i]==1)
  24.         {
  25.             if(color[i]==WHITE)
  26.             {
  27.                 dfs_visit(i);
  28.             }
  29.         }
  30.     }
  31.     color[x]=BLACK;
  32.  
  33.     Ftime[x]=Time;
  34.     ++Time;
  35.  }
  36.  
  37.  void dfs()
  38.  {
  39.     for(int i=0; i<node; i++)
  40.     {
  41.         color[i]=WHITE;
  42.     }
  43.  
  44.     for(int i=0; i<node; i++)
  45.     {
  46.         if(color[i]==WHITE)
  47.         {
  48.             dfs_visit(i);
  49.         }
  50.     }
  51.  }
  52.  
  53.  int main()
  54.  {
  55.     freopen("input.txt","r",stdin);
  56.     cin>>node>>edge;
  57.  
  58.     int n1,n2;
  59.     for(int i=0; i<edge; i++)
  60.     {
  61.         cin>>n1>>n2;
  62.         adj[n1][n2]=1;
  63.         adj[n2][n1]=1;
  64.     }
  65.  
  66.     dfs();
  67.  
  68.     cout<<"\n";
  69.  
  70.     for(int i=0; i<node; i++)
  71.     {
  72.         cout<<"Node: "<<(char)('A'+i)<<" "<<Stime[i]<<" "<<Ftime[i]<<endl;
  73.     }
  74.     return 0;
  75.  }
Add Comment
Please, Sign In to add comment