ltpq_cses_round_trip

Using characteristics of DFS to trace the path.
mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.4 kB
1
Indexable
Never
#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");
}