ltpq_cses_round_trip
Using characteristics of DFS to trace the path.unknown
c_cpp
3 years ago
1.4 kB
7
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...