P3916 图的遍历

知识点：图的遍历

难度：3

这个题如果暴力做，那么肯定会超时，正确的方法是建立反向边，然后从大的边向小的边进行遍历，然后深搜，看看能到达哪个点，那个点能到的最大的点就是一开始深搜的点，刚刚开始学习图，这个思想估计很重要，没见哪本书上系统的写过

#include 
 
using namespace std;
 
const int N = 1e5 + 5;
 
int n, m, tot, ver[N], nxt[N], head[N], rec[N], vis[N];
 
void add(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x]; head[x] = tot;
}
 
void dfs(int u, int x) {
	vis[u] = 1;
	rec[u] = x;
	for (int i = head[u]; i; i = nxt[i]) {
		int y = ver[i];
		if (!vis[y]) dfs(y, x);
	}
}
 
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		add(y, x);
	}
	for (int i = n; i >= 1; i--) {
		if (!vis[i]) dfs(i, i);
	}
	for (int i = 1; i <= n; i++) {
		cout << rec[i] << (i < n ? " " : "\n");
	}
	return 0;
}