CSES Problem Set Round Trip Solution

 

 Problem Link:  https://cses.fi/problemset/task/1669/

Solution in C++:

/// La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

/// Abul Hasnat Tonmoy

/// Department of CSE,23rd batch

/// Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 9;

vector<int> g[N];

int vis[N], parent[N];

int col[N], src, des;

int n, m;

bool cycle;

bool dfs(int u, int p) {

vis[u] = 1;

parent[u] = p;

for (auto v : g[u]) {

if (v == p) continue;

if (vis[v] == 1) {

src = v;

des = u;

return true;

}

if (vis[v] == 0) {

if (dfs(v, u)) return true;

}

}

return false;

}

bool visit_all() {

for (int i = 1; i <= n; i++) {

if (vis[i] == 0)

if (dfs(i, -1)) return true;

}

return false;

}

int32_t main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cin >> n >> m;

for (int i = 0; i < m; i++) {

int u, v;

cin >> u >> v;

g[u].push_back(v);

g[v].push_back(u);

}

if (visit_all() == false) {

cout << "IMPOSSIBLE" << endl;

return 0;

}

int tm = des;

vector<int> ans;

ans.push_back(des);

while (tm != src) {

ans.push_back(parent[tm]);

tm = parent[tm];

}

ans.push_back(des);

cout << ans.size() << endl;

for (auto i : ans) {

cout << i << " ";

}

return 0;

}