karbaev

STL DFS

Nov 4th, 2014
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <vector>
  5. #include <limits>
  6. #define MAX 101
  7. using namespace std;
  8.  
  9. enum colors {BLACK, WHITE, GRAY};
  10. int color[MAX], d[MAX], p[MAX], f[MAX], t, vertex, edge;
  11. int NIL = numeric_limits<int>::min();
  12.  
  13. void DFS(vector<int>[]);
  14. void DFS_VISIT(vector<int>[],int);
  15.  
  16. int main(void)
  17. {
  18.     //freopen("dfs.txt", "r", stdin);
  19.     vector<int> adjList[MAX];
  20.     int u, v;
  21.     cin >> vertex >> edge;
  22.     for(int e=1; e<=edge; e++) {
  23.         cin >> u >> v;
  24.         adjList[u].push_back(v);
  25.     }
  26.     DFS(adjList);
  27.     for(int v=1; v<=vertex; v++) {
  28.         printf("v%d (%d/%d)\n", v, d[v], f[v]);
  29.     }
  30.     return 0;
  31. }
  32.  
  33. void DFS(vector<int> G[]) {
  34.     for(int u=0; u<=vertex; u++) {
  35.         color[u] = WHITE;
  36.         p[u] = NIL;
  37.     }
  38.     t = 0;
  39.     for(int u=1; u<=vertex; u++) {
  40.         if(color[u] == WHITE) {
  41.             DFS_VISIT(G,u);
  42.         }
  43.     }
  44. }
  45.  
  46. void DFS_VISIT(vector<int> G[], int u) {
  47.     t = t + 1;
  48.     d[u] = t;
  49.     color[u] = GRAY;
  50.     for(int v=0; v<G[u].size(); v++) {
  51.         if(color[G[u][v]] == WHITE) {
  52.             p[G[u][v]] = u;
  53.             DFS_VISIT(G,G[u][v]);
  54.         }
  55.     }
  56.     color[u] = BLACK;
  57.     t = t + 1;
  58.     f[u] = t;
  59. }
  60.  
  61. /* //SAMPLE INPUT
  62. 6 8
  63. 1 2
  64. 1 4
  65. 2 5
  66. 3 5
  67. 3 6
  68. 4 2
  69. 5 4
  70. 6 6
  71. */
Advertisement
Add Comment
Please, Sign In to add comment