洛谷 P3916 图的遍历

题目链接

最容易想的思路：对于每一个点都进行dfs/bfs，时间复杂度为O(n*(n+m))，显然超时

可以使用类似记忆化的操作，一个点能到达的最大值是自己所有能达到的边的最大值，则可以递归来做

但有一个BUG，如果有一个环状，就会无限递归

比如\(1=>2,2=>3,3=>1\)

那就可以换一种方式考虑，从最大的点开始枚举，枚举能到达的点，将其答案设置为当前的点

设置过答案的点在后续枚举的时候就不用更新了，因为是从大到小枚举，最先到的肯定是最大的

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, x, y, ans[MAXN];

vector <int> p[MAXN];

int dfs(int x, int t) { // t是要设置的答案，当前枚举的点

	ans[x] = t;

	for (vector <int> :: iterator it = p[x].begin(); it != p[x].end(); ++it)

		if (!ans[*it]) dfs(*it, t);

}

int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; ++i) scanf("%d%d", &x, &y), p[y].push_back(x);

	for (int i = n; i >= 1; --i)

		if (!ans[i]) dfs(i, i);

	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);

	return 0;

}

巴特西

洛谷 P3916 图的遍历

最新文章

热门文章