Advertisement
i_love_rao_khushboo

Untitled

Aug 8th, 2022
831
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.97 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define mp make_pair
  10. #define F first
  11. #define S second
  12. #define PI 3.1415926535897932384626
  13. #define sz(x) ((int)(x).size())
  14.  
  15. typedef pair<int, int> pii;
  16. typedef pair<ll, ll> pll;
  17. typedef vector<int> vi;
  18. typedef vector<ll> vll;
  19. typedef vector<ull> vull;
  20. typedef vector<bool> vb;
  21. typedef vector<char> vc;
  22. typedef vector<string> vs;
  23. typedef vector<pii> vpii;
  24. typedef vector<pll> vpll;
  25. typedef vector<vi> vvi;
  26. typedef vector<vll> vvll;
  27. typedef vector<vull> vvull;
  28. typedef vector<vb> vvb;
  29. typedef vector<vc> vvc;
  30. typedef vector<vs> vvs;
  31.  
  32. /************************************************** DEBUGGER *******************************************************************************************************/
  33.  
  34. #ifndef ONLINE_JUDGE
  35. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  36. #else
  37. #define debug(x)
  38. #endif
  39.  
  40. void _print(ll t) { cerr << t; }
  41. void _print(int t) { cerr << t; }
  42. void _print(string t) { cerr << t; }
  43. void _print(char t) { cerr << t; }
  44. void _print(ld t) { cerr << t; }
  45. void _print(double t) { cerr << t; }
  46. void _print(ull t) { cerr << t; }
  47.  
  48. template <class T, class V> void _print(pair <T, V> p);
  49. template <class T> void _print(vector <T> v);
  50. template <class T> void _print(vector <vector<T>> v);
  51. template <class T> void _print(set <T> v);
  52. template <class T, class V> void _print(map <T, V> v);
  53. template <class T> void _print(multiset <T> v);
  54. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  55. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  56. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  57. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  58. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  59. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  60.  
  61. /*******************************************************************************************************************************************************************/
  62.  
  63. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  64. int rng(int lim) {
  65.     uniform_int_distribution<int> uid(0,lim-1);
  66.     return uid(rang);
  67. }
  68.  
  69. const int INF = 0x3f3f3f3f;
  70. const int mod = 1e9+7;
  71.  
  72. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  73.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  74.                          
  75. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  76. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  77.  
  78. /******************************************************************************************************************************/
  79.  
  80. // stores the input graph
  81. vvi g;
  82.  
  83. // to keep track of visited vertices
  84. vb vis;
  85.  
  86. int n, m;
  87.  
  88. void dfs_helper(int cur, vi &res) {
  89.     // marking a node visited as soon as it is pushed in internal call stack
  90.     vis[cur] = 1;
  91.  
  92.     // push src in the result
  93.     res.pb(cur);
  94.    
  95.     // go to all the unvisited nodes of the current node, but one by one
  96.     for(auto x: g[cur]) {
  97.         // check if already visited or not
  98.         if(!vis[x]) {
  99.             // push it in the stack(internal call stack is used)
  100.             dfs_helper(x, res);
  101.         }
  102.     }
  103. }
  104.  
  105. vi dfs(int src) {
  106.     // to store one of the many possible dfs traversal, using source(starting vertex) as src
  107.     vi res;
  108.    
  109.     // marking all nodes as unvisited initially
  110.     for(int i = 0; i < n; i++) vis[i] = 0;
  111.  
  112.     dfs_helper(src, res);
  113.  
  114.     // return the final result of traversal
  115.     return res;
  116. }
  117.  
  118. void solve()
  119. {
  120.     cin >> n >> m;
  121.    
  122.     g.clear(); g.resize(n);
  123.     vis.clear(); vis.resize(n, 0);
  124.    
  125.     // 0-based vertices
  126.     for(int i = 0; i < m; i++) {
  127.         int x, y; cin >> x >> y;
  128.         g[x].pb(y);
  129.         g[y].pb(x);
  130.     }
  131.        
  132.     vi res = dfs(0);
  133.    
  134.     for(auto x: res) cout << x << " ";
  135.     cout << "\n";
  136. }
  137.  
  138. int main()
  139. {
  140.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  141.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  142.  
  143.     // #ifndef ONLINE_JUDGE
  144.     //     freopen("input.txt", "r", stdin);
  145.     //     freopen("output.txt", "w", stdout);
  146.     // #endif
  147.    
  148.     // #ifndef ONLINE_JUDGE
  149.     //      freopen("error.txt", "w", stderr);
  150.     // #endif
  151.    
  152.     int t = 1;
  153.     // int test = 1;
  154.     // cin >> t;
  155.     while(t--) {
  156.         // cout << "Case #" << test++ << ": ";
  157.         solve();
  158.     }
  159.  
  160.     return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement