SHARE
TWEET

Untitled




Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <cstdio>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <set>
- #include <unordered_set>
- #include <map>
- #include <unordered_map>
- #include <random>
- #include <ctime>
- #include <utility>
- #include <fstream>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- #pragma comment(linker, "/STACK:256000000")
- #pragma warning(disable:4996)
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- const char el = '\n';
- const int inf = 1e9;
- const ll llinf = 1e18, mod = 1000'000'007ll;
- const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
- #define forn(i, n) for (int i = 0; i < (int)n; ++i)
- #define firn(i, n) for (int i = 1; i < (int)n; ++i)
- #define all(v) v.begin(), v.end()
- #define x first
- #define y second
- template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
- template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
- template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << '\n'; }
- template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }
- mt19937 rnd(time(NULL));
- vector<pair<int, int>> g[100000];
- struct edge {
- int v, u;
- bool k;
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int n, m;
- cin >> n >> m;
- vector<int> r(n, 0);
- vector<edge> a(m);
- forn(i, m) {
- int v, u;
- cin >> v >> u;
- v--; u--;
- a[i] = { v, u, 1 };
- g[v].push_back({ u, i });
- g[u].push_back({ v, i });
- }
- vector<int> q, ans;
- q.push_back(0);
- while (!q.empty()) {
- int v = q.back();
- while (r[v] < (int)g[v].size() && !a[g[v][r[v]].y].k) r[v]++;
- if (r[v] < (int)g[v].size()) {
- q.push_back(g[v][r[v]].x);
- a[g[v][r[v]].y].k = 0;
- r[v]++;
- }
- else {
- ans.push_back(v + 1);
- q.pop_back();
- }
- }
- output(ans);
- #ifdef _DEBUG
- system("pause");
- #endif
- return 0;
- }
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.