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 dfs(int u) {
31 cout << u << " ";
32 // Danh dau la u da duoc ghe tham
33 visited[u] = true;
34 for(int v: adj[u]) {
35 // Neu dinh v chua duoc tham
36 if(!visited[v]) {
37 parent[v] = u; // Ghi nhan cha cua v la u
38 dfs(v);
39 }
40 }
41}
42
43void path(int s, int t) {
44 memset(visited, false, sizeof(visited));
45 memset(parent, 0, sizeof(parent));
46 cout << "DFS: ";
47 dfs(s);
48 cout << endl;
49
50 cout << "Path: ";
51 if(!visited[t]) {
52 cout << "Khong co duong di tu " << s << " den " << t;
53 }
54 else {
55 // Truy vet duong di
56 vector<int> path;
57 // Bat dau di nguoc tu dinh t
58 while(t != s) {
59 path.push_back(t);
60 t = parent[t]; // Lan nguoc lai
61 }
62 path.push_back(s);
63 reverse(path.begin(), path.end());
64
65 // In duong di
66 for(int x: path) {
67 cout << x << " ";
68 }
69 }
70}
71
72int main() {
73 // Chuyen NHAP, XUAT thanh file
74 freopen("lab_2_2_input.INP", "r", stdin);
75 freopen("lab_2_2_output.OUT", "w", stdout);
76
77 // INPUT
78 inp();
79
80 // Duong di tu dinh s -> dinh t
81 path(s, t);
82}