P5318【深基18.例3】查找文献

第一行DFS，1-2-5-回溯-6-回溯-回溯-3-7-8-回溯-回溯-回溯-4

代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 100005;
int n, m;
vector<int>p[MAXN];
bool u[MAXN];
void solve(int x) {cout << x << " ";for (int i = 0, sz = p[x].size(); i < sz; i++) {if (!u[p[x][i]]) {u[p[x][i]] = true;solve(p[x][i]);}}
}
int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;p[x].push_back(y);}u[1] = true;solve(1);return 0;
}

第二行BFS，1-2-回溯-3-回溯-4-回溯-（2）-5-回溯-6-回溯-回溯-（3）-7-8

代码如下：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 100005;
int n, m;
vector<int>p[MAXN];
queue<int>q;
bool u[MAXN];
int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;p[x].push_back(y);}u[1] = true;q.push(1);while (!q.empty()) {int x=q.front();q.pop();cout << x << " ";for (int i = 0, sz = p[x].size(); i < sz; i++) {if (!u[p[x][i]]) {u[p[x][i]] = true;q.push(p[x][i]);}}}return 0;
}