fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. const int MAXN=500005;
  8. const int INF=1e9;
  9. vector<int> adj[MAXN];
  10. int dist[MAXN];
  11. int parent[MAXN];
  12.  
  13.  
  14. void bfs(int a, int n){
  15.  
  16. 	for(int i=1; i<n+1; i++){
  17. 		dist[i]=INF;
  18. 		parent[i]=-1;
  19. 	}
  20.  
  21. 	queue <int> q;
  22.  
  23. 	dist[a]=0;
  24. 	q.push(a);
  25.  
  26.  
  27. 	while(!q.empty()){
  28. 		int v=q.front();
  29. 		q.pop();
  30.  
  31. 		for(int u: adj[v]){
  32. 			if(dist[u]==INF){
  33. 				dist[u]=dist[v]+1;
  34. 				parent[u]=v;
  35. 				q.push(u);
  36. 			}
  37. 		}
  38. 	}
  39. }
  40.  
  41. vector<int> scie(int k){
  42. 	if(dist[k]==INF)
  43. 	return {};
  44.  
  45. 	vector<int> path;
  46. 	for(int v=k; v!=-1; v=parent[v])
  47. 	path.push_back(v);
  48.  
  49. 	reverse(path.begin(), path.end());
  50. 	return path;
  51. }
  52.  
  53.  
  54. int main() {
  55. 	ios_base::sync_with_stdio(false);
  56. 	cin.tie(NULL);
  57. int n,m;
  58. cin>>n>>m;
  59. for(int i=0; i<m; i++){
  60. 	int a,b;
  61. 	cin>>a>>b;
  62. 	adj[a].push_back(b);
  63. 	adj[b].push_back(a);
  64. }
  65.  
  66. int start=1;
  67. int target=n;
  68. bfs(start, target);
  69.  
  70.  
  71.  
  72.  
  73.  
  74. 	return 0;
  75. }
Success #stdin #stdout 0.01s 18092KB
comments (?)
stdin
copy 
5 6
1 2
1 3
2 4
4 6
5 6
2 3
stdout
copy 
Standard output is empty
https://ideone.com/4VRfF1
language:
C++14 (gcc 8.3)
created:
7 hours 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!