Walk In a Graph

editorial
, ,
1

#Problem link:
[Practice] CENV005 Problem - CodeChef
[Codennovate] CodeChef: Practical coding for everyone

Author: [Abhishek Patnigere] stingray8041 | CodeChef User Profile for Abhishek Patnigere | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: Hard
# PREREQUISITES: Graphs,Math

Solution To The Problem

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,start,end) for(int i=start; i<=end; i++)
#define repd(i,start,end) for(int i=start; i>=end; i–)
#define all(x) x.begin(),x.end()
#define debug(x) cout << “(” << #x << ": " << x << “)” << endl;
#define maxn 1000005

vector adj[maxn];
int udist[maxn], vdist[maxn];

void bfs(int root, int n, int distance[]) {
vector visited(n,false);
visited[root]=true;
distance[root]=0;
queue q;
q.push(root);

while(!q.empty()) {
	int node = q.front();
	q.pop();

	for(int u: adj[node]) {
		if(!visited[u]) {
			visited[u] = true;
			distance[u] = distance[node]+1;
			q.push(u);
		}
	}
}

}

void solve() {
int n,m,u,v;
cin >> n >> m >> u >> v;

rep(i,m) {
	int x,y;
	cin >> x >> y;
	adj[x].pb(y);
	adj[y].pb(x);
}

if(u==v) {
	cout << "possible\n";
	cout << 0 << endl;
	cout << u << endl; 
	return;
}

rep(i,n) {
	if(adj[i].size()==0 || find(all(adj[i]),u)==adj[i].end() || find(all(adj[i]),v)==adj[i].end()) {
		udist[i]=1e8;
		vdist[i]=1e8;
	}
	else {
		udist[i]=0;
		vdist[i]=0;
	}
}

bfs(u,n,udist);
bfs(v,n,vdist);

int path_length=1e8;
bool flag=0;

map<int, vector<int>> ans; //distance to node map

for(int i=0; i<n; i++) {
	if(udist[i]!=1e8 && vdist[i]!=1e8) {
		if(udist[i]==vdist[i]) {
			flag=1;
			path_length = min(path_length, udist[i]);
			ans[udist[i]].pb(i);
		}

		else if(udist[i]>vdist[i]) {
			int req = udist[i];

			if( (udist[i]-vdist[i])%2 == 0) {
				flag=1;
				path_length = min(path_length, req);
				ans[req].pb(i);
				continue;
			}

			int parity = vdist[i]%2;
			//search if path length of req from node v to i
			for(int x: adj[i]) {
				if(vdist[x] < req) {
					if(vdist[x]%2 == parity) {
						flag=1;
						path_length = min(path_length, req);
						ans[req].pb(i);
						break;
					}
				}
			}
		}

		else {
			int req = vdist[i];

			if( (vdist[i]-udist[i])%2 == 0) {
				flag=1;
				path_length = min(path_length, req);
				ans[req].pb(i);
				continue;
			}

			int parity = udist[i]%2;
			//search if path length of req from node u to i
			for(int x: adj[i]) {
				if(udist[x] < req) {
					if(udist[x]%2 == parity) {
						flag=1;
						path_length = min(path_length, req);
						ans[req].pb(i);
						break;
					}
				}
			}
		}
	}
}

if(flag) {
	cout << "possible" << endl;
	cout << path_length << endl;
	for(auto x: ans[path_length]) {
		cout << x << " ";
	}
	cout << endl;
}

else
	cout << "impossible" << endl;

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}