Advertisement
arfin97

Algo - Simple DFS(Depth First Search) - V1.0

Jun 5th, 2018
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define d(x)                cout << #x << " = " << (x) << endl;
  4. #define fr                  freopen("in.txt", "r", stdin);
  5. #define fw                  freopen("out.txt", "w", stdout);
  6. #define mem(x)              memset((x), 0, sizeof((x)));
  7. #define pb                  push_back
  8. #define LL                  long long
  9. #define fastIO              ios_base::sync_with_stdio(false)
  10. #define sf                  scanf
  11. #define pf                  printf
  12. #define sc1(x)              scanf("%d", &x)
  13. #define sc2(x, y)           scanf("%d %d", &x, &y)
  14. #define sc3(x, y, z)        scanf("%d %d %d", &x, &y, &z)
  15. #define FOR(i, x, y)        for(int i=int(x); i<int(y); i++)
  16. #define ROF(i, x, y)        for(int i=int(x-1); i>=int(y); i--)
  17. #define all(c)              c.begin(), c.end()
  18. #define unq(v)              sort(all(v)), (v).erase(unique(all(v)),v.end())
  19. #define siz 1000000
  20. #define MAX 100000
  21.  
  22. //Graph
  23. vector<int> edge[MAX];
  24. vector<int> cost[MAX];
  25. //DFS visited node: colors: 0=white, 1=gray, 2=black
  26. vector<int> visited(MAX);
  27. //DFS validator
  28. int max_depth = 0;
  29.  
  30. /////////////////DFS/////////////////////////
  31. void DFS(int u){
  32.     visited[u] = 1;
  33.     for(int v = 0; v < edge[u].size(); v++){
  34.         if(visited[edge[u][v]] == 0){
  35.             DFS(edge[u][v]);
  36.             max_depth++;
  37.         }
  38.     }
  39.     visited[u] = 2;
  40. }
  41. ////////////////////////////////////////////
  42.  
  43. int main(){
  44.     fastIO;
  45.     fw; fr;
  46.     int n, e;
  47.     cin >> n >> e;
  48.     for(int i = 0; i < e; i++){
  49.         int x, y;
  50.         cin >> x >> y;
  51.         edge[x].push_back(y);
  52.         edge[y].push_back(x);
  53.         cost[x].push_back(1);
  54.         cost[y].push_back(1);
  55.     }
  56.  
  57.     //printing graph
  58.     for(int i = 1; i <= n; i++){
  59.         cout << "Node: " << i << endl;
  60.         cout << "Connected with: ";
  61.         for(int j = 0; j < edge[i].size(); j++){
  62.             cout << edge[i][j] << " ";
  63.         }
  64.         cout << endl;
  65.     }
  66.  
  67.     //running DFSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSs
  68.     DFS(1);
  69.     d(max_depth);
  70.  
  71.     return 0;
  72. }
  73.  
  74. //test case
  75. /*
  76. 6 5
  77. 1 2
  78. 2 3
  79. 3 4
  80. 4 5
  81. 5 6
  82. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement