1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4
5int n, m; // n: so dinh, m: so canh
6int s, t; // s: dinh bat dau, t: dinh ket thuc
7vector<int> adj[1001];
8bool visited[1001];
9int parent[1001];
10
11void inp() {
12 cin >> n >> m >> s >> t;
13 for(int i = 0; i < m; i++) {
14 int x, y;
15 cin >> x >> y;
16 adj[x].push_back(y);
17
18 // Do thi co huong thi comment dong code sau
19 // adj[y].push_back(x);
20 }
21
22 // Sap xep cac gia tri trong vector tang dan A-Z
23 for(int i = 1; i <= n; i++) {
24 sort(adj[i].begin(), adj[i].end());
25 }
26
27 memset(visited, false, sizeof(visited));
28}
29
30void bfs(int u) {
31 // Khoi tao
32 queue<int> q;
33 q.push(u);
34 visited[u] = true;
35
36 // Lap
37 while(!q.empty()) {
38 int v = q.front(); // Lay phan tu o dau hang doi
39 q.pop(); // xoa bo phan tu o dau ra khoi hang doi
40 cout << v << " ";
41 for(int x: adj[v]) {
42 if(!visited[x]) {
43 q.push(x);
44 visited[x] = true;
45 parent[x] = v; // Ghi nhan cha cua x la v
46 }
47 }
48 }
49}
50
51void path(int s, int t) {
52 memset(visited, false, sizeof(visited));
53 memset(parent, 0, sizeof(parent));
54
55 cout << "BFS: ";
56 bfs(s);
57 cout << endl;
58
59 cout << "Path: ";
60 if(!visited[t]) {
61 cout << "Khong co duong di tu " << s << " den " << t;
62 }
63 else {
64 // Truy vet duong di
65 vector<int> path;
66 // Bat dau di nguoc tu dinh t
67 while(t != s) {
68 path.push_back(t);
69 t = parent[t]; // Lan nguoc lai
70 }
71 path.push_back(s);
72 reverse(path.begin(), path.end());
73
74 // In duong di
75 for(int x: path) {
76 cout << x << " ";
77 }
78 }
79}
80
81int main() {
82 // Chuyen NHAP, XUAT thanh file
83 freopen("lab_3_2_input.INP", "r", stdin);
84 freopen("lab_3_2_output.OUT", "w", stdout);
85
86 // INPUT
87 inp();
88
89 // Duong di tu dinh s -> dinh t
90 path(s, t);
91}