洛谷 P3916 【图的遍历】

这道题绿题有点高了吧...

我一开始的思路就是一个暴力的遍历，用递归加一个记忆化，对于一个点不断的往下搜索，然后确定最大的，返回，给上面的节点。就在这个过程中，我们是搜到最大的数然后返回给上层的数，那我们为什么不直接从大的出发，那么大的那个数到达的点也就必然能达到这个大的数，这个很好实现，直接反向建图，从大开始遍历，遍历到达的点ans值直接就为这个数。这样，我写下了我的第一代程序，超时了，八十分。

#include <bits/stdc++.h>

using namespace std;

int n , m;

int ans[100010] , vis[100010];

vector<int> e[100010];

void dfs(int k , int step){

	if(vis[step] || ans[step] >= k) return;

	vis[step] = 1;

	if(!ans[step] || ans[step] < k) ans[step] = k;

	for(int i = 0; i < e[step].size(); i++) dfs(k , e[step][i]);

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= m; i++){

		int x , y;

		cin >> x >> y;

		e[y].push_back(x);

	}

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

		memset(vis , 0 , sizeof(vis));

		dfs(i , i);

	}

	for(int i = 1; i <= n; i++) cout << ans[i] << " ";

	return 0;

}

为什么会超时呢，注意到，我们是从大的开始跑的，从大到小枚举，那么这个数之前就被遍历过了的话，现在再次遍历到时，一定是小于之前遍历时保存的数，这样，就可以写下最终的代码：

#include <bits/stdc++.h>

using namespace std;

int n , m;

int ans[100010] , vis[100010];

vector<int> e[100010];

void dfs(int k , int step){

	if(vis[step]) return;

	vis[step] = 1;

	ans[step] = k;

	for(int i = 0; i < e[step].size(); i++) dfs(k , e[step][i]);

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= m; i++){

		int x , y;

		cin >> x >> y;

		e[y].push_back(x);

	}

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

	for(int i = 1; i <= n; i++) cout << ans[i] << " ";

	return 0;

}

巴特西

洛谷 P3916 【图的遍历】

最新文章

热门文章