daily pastebin goal
5%
SHARE
TWEET

Untitled

a guest Jan 24th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <queue>
  8. #include <deque>
  9. #include <bitset>
  10. #include <set>
  11. #include <unordered_set>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <random>
  15. #include <ctime>
  16. #include <utility>
  17. #include <fstream>
  18.  
  19. #pragma GCC optimize("Ofast")
  20. #pragma GCC optimize("no-stack-protector")
  21. #pragma GCC optimize("unroll-loops")
  22. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  23. #pragma GCC optimize("fast-math")
  24. #pragma comment(linker, "/STACK:256000000")
  25. #pragma warning(disable:4996)
  26.  
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31.  
  32. const char el = '\n';
  33. const int inf = 1e9;
  34. const ll llinf = 1e18, mod = 1000'000'007ll;
  35. const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
  36.  
  37. #define forn(i, n) for (int i = 0; i < (int)n; ++i)
  38. #define firn(i, n) for (int i = 1; i < (int)n; ++i)
  39. #define all(v) v.begin(), v.end()
  40. #define x first
  41. #define y second
  42.  
  43. template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
  44. template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
  45. template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << '\n'; }
  46. template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }
  47.  
  48. mt19937 rnd(time(NULL));
  49.  
  50. vector<pair<int, int>> g[100000];
  51.  
  52. struct edge {
  53.     int v, u;
  54.     bool k;
  55. };
  56.  
  57. int main() {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(NULL);
  60.     int n, m;
  61.     cin >> n >> m;
  62.     vector<int> r(n, 0);
  63.     vector<edge> a(m);
  64.     forn(i, m) {
  65.         int v, u;
  66.         cin >> v >> u;
  67.         v--; u--;
  68.         a[i] = { v, u, 1 };
  69.         g[v].push_back({ u, i });
  70.         g[u].push_back({ v, i });
  71.     }
  72.     vector<int> q, ans;
  73.     q.push_back(0);
  74.     while (!q.empty()) {
  75.         int v = q.back();
  76.         while (r[v] < (int)g[v].size() && !a[g[v][r[v]].y].k) r[v]++;
  77.         if (r[v] < (int)g[v].size()) {
  78.             q.push_back(g[v][r[v]].x);
  79.             a[g[v][r[v]].y].k = 0;
  80.             r[v]++;
  81.         }
  82.         else {
  83.             ans.push_back(v + 1);
  84.             q.pop_back();
  85.         }
  86.     }
  87.     output(ans);
  88. #ifdef _DEBUG
  89.     system("pause");
  90. #endif
  91.     return 0;
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top