ltpq_cses_round_trip
Using characteristics of DFS to trace the path.unknown
c_cpp
2 years ago
1.4 kB
5
Indexable
#include<bits/stdc++.h> using namespace std; const int MOD = 2004010501; typedef long long Int; typedef long double Real; #define DBG(x) cerr << #x << " = " << x << ' '; #define DBGn(x) cerr << #x << " = " << x << '\n'; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> T random(const T& l, const T& r) { return uniform_int_distribution<T>(l,r)(rng); } template<typename T> void maximize(T& var, const T& val) { if (val > var) var = val; } template<typename T> void minimize(T& var, const T& val) { if (val < var) var = val; } const int N = 1e5 + 50; vector<int> adj[N]; bool vis[N]; int pa[N]; void dfs(int u) { vis[u] = 1; for (auto v : adj[u]) if (v != pa[u]) { if (!vis[v]) pa[v] = u, dfs(v); else { vector<int> path; path.push_back(v); do { path.push_back(u); if (u == v) break; u = pa[u]; } while (1); cout << path.size() << '\n'; for (auto x : path) cout << x << ' '; cout << '\n'; exit(0); } } } int main() { #define task "" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int n,m; scanf("%d%d", &n, &m); while (m --> 0) { int u,v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } for (int u = 1; u <= n; u++) if (!vis[u]) dfs(u); puts("IMPOSSIBLE"); }
Editor is loading...