Advertisement
shabbyheart

DFS by Color

Dec 7th, 2019
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string color[100000] = "white";
  4. int timee = 0;
  5. int d[100000],f[100000];
  6. class Node{
  7. public:
  8.     int destination;
  9.     int weight;
  10.     Node *next;
  11. };
  12. class Integer{
  13. public:
  14.     Node *head = NULL;
  15. };
  16.  
  17. void addEdge(Integer arr[],int sorc,int dest)
  18. {
  19.     Node *newNode = new Node();
  20.     newNode->destination = dest;
  21.     newNode->next = NULL;
  22.     if( arr[sorc].head == NULL)
  23.         arr[sorc].head = newNode;
  24.     else
  25.     {
  26.         Node *temp = arr[sorc].head;
  27.         while(temp->next != NULL)
  28.             temp = temp->next;
  29.         temp->next = newNode;
  30.     }
  31. }
  32. void DFS_Visit(Integer arr[],int s,int prev[])
  33. {
  34.     color[s] = "Gray";
  35.     timee++;
  36.     d[s] = timee;
  37.     Node *temp = arr[s].head;
  38.     cout<<s<< " "<<endl;
  39.     while( temp!=NULL)
  40.     {
  41.         int child = temp->destination;
  42.         if( color[child] == "white")
  43.         {
  44.             prev[child] = s;
  45.             DFS_Visit(arr,child,prev);
  46.         }
  47.         temp = temp->next;
  48.     }
  49.     color[s] = "Black";
  50.     timee = timee+1;
  51.     f[s] = timee;
  52. }
  53. void DFS(Integer arr[],int prev[],int v){
  54.     for(int i=1; i<=v; i++)
  55.     {
  56.         if(color[i] == "white")
  57.             DFS_Visit(arr,i,prev);
  58.     }
  59. }
  60. int main()
  61. {
  62.     int prev[100000] = {0};
  63.     freopen("input.txt","r",stdin);
  64.     int v;
  65.     cin>>v;
  66.     Integer arr[v];
  67.  
  68.     /// eita na korle arr er vitore v+1 dite hobe
  69.      for (int i = 0; i <= v; i++)
  70.         arr[i].head = NULL;
  71.  
  72.     /// getting input
  73.     int m,n;
  74.     while(scanf("%d%d",&m,&n) == 2)
  75.     {
  76.         addEdge(arr,m,n);
  77.         //addEdge(arr,n,m);
  78.     }
  79.     DFS(arr,prev,v);
  80.     cout<<d[7]<<" "<<f[7]<<" "<<prev[7]<<endl;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement