Round Trip

Problem Link: Round Trip

Resources:

Checking a graph for acyclicity and finding a cycle in O(M) 

Detect cycle in an undirected graph using BFS 

Detect cycle in an undirected graph 

 

Implementation:

	///https://cses.fi/problemset/task/1669/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 1000005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	const ll mod = 1e9 + 7;
	inline void normal(ll &a) { a %= mod; (a < 0) && (a += mod); }
	inline ll modMul(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
	inline ll modAdd(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
	inline ll modSub(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
	inline ll modPow(ll b, ll p) { ll r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
	inline ll modInverse(ll a) { return modPow(a, mod - 2); }
	inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
	///**
	template < typename F, typename S >
	ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << *it;
	}
	return os << "}";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin()) os << ", ";
	os << *it;
	}
	return os << "]";
	}
	template < typename F, typename S >
	ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << it -> first << " = " << it -> second ;
	}
	return os << "]";
	}
	#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
	clock_t tStart = clock();
	#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
	void faltu () { cerr << endl; }
	template <typename T>
	void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
	}
	template <typename T, typename ... hello>
	void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
	// Program showing a policy-based data structure.
	#include <ext/pb_ds/assoc_container.hpp> // Common file
	#include <ext/pb_ds/tree_policy.hpp>
	#include <functional> // for less
	#include <iostream>
	using namespace __gnu_pbds;
	using namespace std;
	// GNU link : https://goo.gl/WVDL6g
	typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update>
	new_data_set;
	// find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো!
	// order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়।
	//*//**___________________________________________________**/
	const int N = 1e5 + 5;
	int n;
	vector<int> graph[N];
	vector<int> color;
	vector<int> parent;
	int cycle_start, cycle_end;
	bool dfs(int u, int p = -1)
	{
	//dbg(u);
	color[u] = 1;
	for (auto v : graph[u]) {
	if (v == p) continue;
	if (color[v] == 0) {
	parent[v] = u;
	if (dfs(v, u)) return true;
	}
	else if (color[v] == 1) {
	cycle_start = v;
	cycle_end = u;
	return true;
	}
	}
	color[u] = 2;
	return false;
	}
	void find_cycle() {
	color.assign(n, 0);
	parent.assign(n, -1);
	cycle_start = -1;
	for (int i = 0; i < n; i++) {
	if (color[i] == 0 && dfs(i)) {
	break;
	}
	}
	if (cycle_start == -1) {
	cout << "IMPOSSIBLE";
	}
	else {
	// dbg(cycle_start, cycle_end);
	// dbg(parent[1], parent[3], parent[5]);
	vector<int> cycle;
	cycle.push_back(cycle_start);
	for (int v = cycle_end; v != cycle_start; v = parent[v]) {
	// dbg(v, parent[v]);
	cycle.push_back(v);
	}
	cycle.push_back(cycle_start);
	reverse(cycle.begin(), cycle.end());
	cout << (int)cycle.size() << endl;
	for (auto x : cycle) cout << x + 1 << " ";
	cout << endl;
	}
	}
	int main()
	{
	FASTIO
	/*
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
	int u, v;
	cin >> u >> v;
	--u;
	--v;
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	find_cycle();
	return 0;
	}

view raw RoundTrip.cpp hosted with ❤ by GitHub

 

Share: