Advertisement
adnan_dipta89

DFS Cormen

Oct 17th, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 100000
  3. using namespace std;
  4. enum color {WHITE,GRAY,BLACK};
  5. vector<vector<int>> adjList;
  6. color vertex_color[MAX+1];
  7. int parent[MAX+1];
  8. int vertex_start[MAX+1];
  9. int vertex_end[MAX+1];
  10. int TIME = 0;
  11. int n,m;
  12. void addEdge(int u, int v)
  13. {
  14.     adjList[u].push_back(v);
  15. }
  16. void DFS_VISIT(int u)
  17. {
  18.     TIME = TIME+1;
  19.     vertex_start[u] = TIME;
  20.     vertex_color[u] = GRAY;
  21.     cout << u << " ";
  22.     for(int i = 0; i < adjList[u].size(); i++)
  23.     {
  24.         int v = adjList[u][i];
  25.         if(vertex_color[v] == WHITE)
  26.         {
  27.             parent[v] = u;
  28.             DFS_VISIT(v);
  29.         }
  30.     }
  31.     vertex_color[u] = BLACK;
  32.     TIME = TIME+1;
  33.     vertex_end[u] = TIME;
  34. }
  35. void DFS()
  36. {
  37.     for(int i = 1; i <= n; i++)
  38.     {
  39.         vertex_color[i] = WHITE;
  40.         parent[i] = 0;
  41.     }
  42.     TIME = 0;
  43.     for(int i = 1; i <= n; i++)
  44.     {
  45.         if(vertex_color[i] == WHITE)
  46.             DFS_VISIT(i);
  47.         cout << endl;
  48.     }
  49.     //DFS_VISIT(2);
  50. }
  51. int main()
  52. {
  53.     freopen("a.txt","r",stdin);
  54.     cin >> n >> m;
  55.     adjList.resize(n+1);
  56.     for(int i = 1; i <= m; i++)
  57.     {
  58.         int u,v;
  59.         cin >> u >> v;
  60.         addEdge(u,v);
  61.     }
  62.     DFS();
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement