思路分析

分析存储方法

在图中，最常见的存储方法是以下三种：

邻接矩阵
邻接表
链式前向星

现在我们就来逐一选择一下：

邻接矩阵？我们发现 \(n\) 达到了 \(10^5\)，而邻接矩阵的空间复杂度是 \(\mathcal O(n^2)\) 的，需要开 \(10^{5^2}=10^{10}\) 个 int，差不多需要 \(37\) GiB 空间，最终只会听取 MLE 声一片。
邻接表？这是一个不错的选择，但是~~为了让这篇题解过审~~扩展读者的眼界，所以这篇题解不会使用这种方法。
链式前向星？这种方法的空间复杂度是 \(\mathcal O(m)\)，时间复杂度也是 \(\mathcal O(m)\)，可以通过本题。

链式前向星初始化

模板：

struct {
	struct { // 存储一条边
		int to;
		int next;
	} edge[(int)(1e6+10)]; // edge 存边，开 m 的最大值
	int cnt, head[(int)(1e5+10)]; // head存点，开 n 的最大值
	void clear() { // 清空
		memset(head, -1, sizeof(head)); // 一定要清成-1！！！
		memset(edge, 0, sizeof(edge));
		cnt = 0;
	}
	void add(int u, int v) { // 加边
		edge[cnt].to = v; // to 是到达的点
		edge[cnt].next = head[u]; // next 是与这条边同起点的边，没有即为-1
		head[u] = cnt++;
	}
} Edge;

解决步骤

读完题，我们可以发现解题可以分为以下几步：

读入各条边的数据
排序
链式前向星加边
深搜
广搜

读入各条边的数据

我们可以自定义一个结构体 input，来存储每行读入的两个值。因为读入的是边，所以极限情况下会有\(m_{max}=10^6\) 行，所以数组可以开 \(10^6+10\)，代码如下。

struct input {
	int x, y;
} in[(int)(1e6+10)];

接下来我们读入每行即可。

时间复杂度为 \(\mathcal O(m)\)。

排序

我们应该根据起点排序，如果起点相同则比较终点。代码如下。

sort(in + 1, in + m + 1, [](const input &a, const input &b){
	if (a.x == b.x) return a.y > b.y;
	return a.x > b.x;
});

但是，根据终点排序似乎也能过？

时间复杂度 \(\mathcal O(m\log m)\)，对于 \(m=10^6\) 的数据范围是没有问题的。

链式前向星加边

遍历 \(in\) 数组，每次都在 \(Edge\) 中 add。

for (int i = 1; i <= m; i++)
	Edge.add(in[i].x, in[i].y);

深搜

设计递归状态

我们可以定义 \(dfs_u\) 代表当前正在访问 \(u\) 这个结点。

每次访问时我们都输出这个结点的编号并且扩展出这个结点所能到达的所有结点，继续 dfs。

确定边界条件

这道题基本上没有什么条件限制，只要这个结点没有被访问过，就可以进行访问。

扩展状态

链式前向星的扩展基本上就算是模板了，大家可以细细使用下面这份模板：

for (int i = Edge.head[u]; ~i; i = Edge.edge[i].next)
	dfs(Edge.edge[i].to);

广搜

广搜与深搜基本相同，这里不再详述，细节见代码注释。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
struct {
	struct {
		int to;
		int next;
	} edge[MAXM];
	int cnt, head[MAXN];
	void clear() {
		memset(head, -1, sizeof(head));
		memset(edge, 0, sizeof(edge));
		cnt = 0;
	}
	void add(int u, int v) {
		edge[cnt].to = v;
		edge[cnt].next = head[u];
		head[u] = cnt++;
	}
} Edge;
int n, m;
struct input {
	int x, y;
} in[MAXM];
int vis[MAXN];
void dfs(int u) {
	if (vis[u]) return ; // 判断是否访问过
	cout << u << " ";
	vis[u] = 1; // 标记
	for (int i = Edge.head[u]; ~i; i = Edge.edge[i].next) // 扩展状态
		dfs(Edge.edge[i].to);
}
void bfs() { // 类似深搜
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		auto u = q.front();
		q.pop();
		if (vis[u]) continue;
		cout << u << " ";
		vis[u] = 1;
		for (int i = Edge.head[u]; ~i; i = Edge.edge[i].next)
			q.push(Edge.edge[i].to);
	}
}
int main() {
	Edge.clear();
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> in[i].x >> in[i].y;
	sort(in + 1, in + m + 1, [](const input &a, const input &b){
		if (a.x == b.x) return a.y > b.y;
		return a.x > b.x;
	});
	for (int i = 1; i <= m; i++) Edge.add(in[i].x, in[i].y);
	dfs(1);
	puts(""); // 奇妙的换行方法
	memset(vis, 0, sizeof(vis)); //将标记数组清零
	bfs();
	return 0;
}