Advertisement
newb_ie

path printing

Oct 25th, 2021
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.82 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int maxN = 1000;
  5. vector<int> adj[maxN];
  6. bool visited[maxN];
  7. int parent[maxN];
  8.  
  9. void dfs (int node,int par) {
  10. visited[node] = true;
  11. parent[node] = par;
  12. for (int child : adj[node]) {
  13. if (visited[child] == false) {
  14. dfs(child,node);
  15. }
  16. }
  17. }
  18.  
  19. int main () {
  20. ios::sync_with_stdio(false);
  21. cin.tie(nullptr);
  22. cout.tie(nullptr);
  23. int n, m;
  24. cin >> n >> m;
  25. for (int i = 1; i <= m; ++i) {
  26. int u,v;
  27. cin >> u >> v;
  28. adj[u].push_back(v);
  29. adj[v].push_back(u);
  30. }
  31. dfs(1,-1); //-1 is a termination point
  32. int dest = 6;
  33. vector<int> path;
  34. path.push_back(dest);
  35. while (parent[dest] != source) {
  36. dest = parent[dest];
  37. path.push_back(dest);
  38. }
  39. reverse(path.begin(),path.end());
  40. for (int p : path) cout << p << ' ';
  41. }
  42.  
  43.  
  44.  
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement