• 题面
• 具体思路
  • 0x01 读题分析
  • 0x02 输入和排序
  • 0x03 DFS
  • 0x04 BFS
  • 0x05 完整程序

题面

此题看似是一道图论，实则比较基础。
只要掌握了基础的 DFS/BFS 即可爆切本题。

具体思路

0x01 读题分析

• 请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
• 对图分别进行 DFS 和 BFS，并输出遍历结果。

读到这两句话，我们就可以很清楚地知道此题考点：搜索和图论（有向图遍历）。

有一个小小的细节：

如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

事实上这句话就相当于告诉了我们搜索的优先顺序，即从小到大搜。

0x02 输入和排序

根据上面分析，如果需要排序每一个结点的所有路径，可以使用 vector 数组。
这样的方式比较简单：

// 存储：vector 数组
vector <int> maps[int(1e5) + 1];
// 输入：u 为起点，v 为终点
maps[u].push_back(v);
// 排序：对编号为 i 的每一个结点的路径排序
sort(maps[i].begin(), maps[i].end());

我们可以写出以下程序，实现输入数据和排序：

cin >> n >> m; // 输入 n, m
for(int i = 1; i <= m; i++){
    int u, v;
    cin >> u >> v; // 输入每一条路径
    maps[u].push_back(v); // 离线存储
}
for(int i = 1; i <= n; i++){
	sort(maps[i].begin(), maps[i].end());
}

0x03 DFS

void dfs(int k = 1){ // k：当前遍历的结点编号
	cout << k << " "; // 输出即可
	for(auto i : maps[k]){ // 遍历：以 k 为起点，每一条路径的终点
		if(!vis[i]){ // 如果没访问过就递归（不重复访问）
			vis[i] = true;
			dfs(i);
		}
	}
}

0x04 BFS

void bfs(){
	queue <int> Q;
	vis[1] = true;
	Q.push(1); // 起点入队
	while(!Q.empty()){
		int fr = Q.front(); Q.pop();
		cout << fr << " "; // 输出当前位置
		for(auto i : maps[fr]){ // 遍历：每一条路径
			if(!vis[i]){ // 没访问过
				vis[i] = true;
				Q.push(i);
			}
		}
	}
}

0x05 完整程序

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int n, m;
vector <int> maps[int(1e5) + 1];
bool vis[int(1e5) + 1] = {false, true};

void dfs(int k = 1){
	cout << k << " ";
	for(auto i : maps[k]){
		if(!vis[i]){
			vis[i] = true;
			dfs(i);
		}
	}
}

void bfs(){
	cout << endl;
	queue <int> Q;
	memset(vis, 0, sizeof(vis));
	vis[1] = true;
	Q.push(1);
	while(!Q.empty()){
		int fr = Q.front(); Q.pop();
		cout << fr << " ";
		for(auto i : maps[fr]){
			if(!vis[i]){
				vis[i] = true;
				Q.push(i);
			}
		}
	}
}

int main(){
	ios :: sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        maps[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
		sort(maps[i].begin(), maps[i].end());
	}
	dfs();
	bfs();

	return 0;
}