fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int n,m;
  7. vector<int>ans;
  8. vector<int>parent;
  9.  
  10. void path(int node,int start)
  11. {
  12.  
  13. 	ans.push_back(node);
  14. 	if(node==start)return;
  15. 	path(parent[node],start);
  16. }
  17.  
  18. int main() {
  19.  
  20. cin>>n>>m;
  21. int flag=0;
  22.  
  23. parent.resize(n+1);
  24. parent[0]=1;
  25.  
  26. deque<pair<int,int>>Q;
  27.  
  28. vector<vector<int>>arr(m,vector<int>(2));
  29. vector<vector<int>>adj(n+1);
  30. vector<int>visit(n+1,0);
  31.  
  32. for(int i=0;i<m;i++)
  33. {
  34. 	cin>>arr[i][0]>>arr[i][1];
  35. }
  36.  
  37. for(int i=0;i<m;i++)
  38. {
  39. 	adj[arr[i][1]].push_back(arr[i][0]);
  40. 	adj[arr[i][0]].push_back(arr[i][1]);
  41. }
  42.  
  43. Q.push_back({1,0});
  44.  
  45. while(Q.size())
  46. {
  47. 	int node=Q.front().first;
  48. 	int time=Q.front().second;
  49. 	visit[node]=true;
  50. 	Q.pop_front();
  51.  
  52. 	//cout<<node<<" "<<time<<endl;
  53. 	if(node==n)
  54. 	{
  55. 		path(node,1);
  56. 		reverse(ans.begin(),ans.end());
  57. 		cout<<ans.size()<<endl;
  58. 		for(auto x: ans)cout<<x<<" ";
  59. 		flag=1; break;
  60. 	}
  61.  
  62. 	for(auto x: adj[node])
  63. 	{
  64. 		if(!visit[x])
  65. 		{
  66. 			Q.push_back({x,time+1});
  67. 			visit[x]=true;
  68. 			parent[x]=node;
  69. 		}
  70. 	}
  71. }
  72.  
  73. if(!flag)cout<<"IMPOSSIBLE";
  74. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 5
1 2
1 3
1 4
2 3
5 4
stdout
copy 
3
1 4 5
https://ideone.com/QkA1pB
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!