fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<int> ke[1001];
  4. int m , n; 
  5. int parent[1001];
  6. bool visited[1001];
  7. int kt = 0;
  8. void DFS(int u) {
  9.     visited[u] = true;
  10.     for (int x : ke[u]) {
  11.         if (!visited[x]) {
  12.             parent[x] = u;
  13.             DFS(x);
  14.             kt = x; // C?p nh?t bi?n kt m?i khi tìm th?y m?t d?nh chua du?c tham
  15.         }
  16.     }
  17. }
  18. void BFS(int u){
  19. 	queue<int> q;
  20. 	q.push(u);
  21. 	visited[u] = true;
  22. 	while(!q.empty()){
  23. 		int x = q.front(); q.pop();
  24. 		for(int y : ke[x]){
  25. 			if(!visited[y]){
  26. 				parent[y] = x;
  27. 				q.push(y);
  28. 				visited[y] = true;
  29. 			}
  30. 		}
  31. 	}
  32. }
  33.  
  34. int main(){
  35. 	cin >> m >> n ;
  36. 	int s, t; 
  37. 	cin >> s >> t;
  38. 	for(int i = 1 ; i <= n ; i++){
  39. 		int x,y; 
  40. 		cin >> x >> y;
  41. 		ke[x].push_back(y);
  42. 	}
  43. 	for(int i = 1 ; i <= n ; i++){
  44. 		sort(ke[i].begin(),ke[i].end());
  45. 	}
  46. 	BFS(s);
  47. 	if(!visited[t]){
  48. 		cout << "-1";
  49. 		return 0;
  50. 	}
  51. 	else{
  52. 		vector<int> path;
  53. 		while(s != t){
  54. 			path.push_back(t);
  55. 			t = parent[t];
  56. 		}
  57. 		path.push_back(s);
  58. 		reverse(path.begin(),path.end());
  59. 		for(int x : path){
  60. 			cout << x << " ";
  61. 		}
  62. 	}
  63. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
5 10 2 3
5 1
4 5
3 5
4 3
2 1
3 2
5 3
2 5
1 3
5 2
stdout
copy 
2 1 3
https://ideone.com/9TeqNJ
[Graph]. Bài 17. Đường đi trên đồ thị có hướng bằng BFS
language:
C++ (gcc 8.3)
created:
12 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!