来自一名蒟蒻的小小疑问
查看原帖
来自一名蒟蒻的小小疑问
1189047
Creeperawwman楼主2024/8/2 20:50

本蒟蒻虽然已经把这道题给过了,但仍有一个小疑问

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> pre[100050];
int dp[100500];
void init() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		pre[b].push_back(a);
	}
}
int dfs(int x, int y) {
	if (dp[x])	return 0;
	dp[x] = max(dp[x], y);
	for (int i = 0; i < pre[x].size(); i++) {
		dfs(pre[x][i], y);
	}
}
void solve() {
	for (int i = n; i >= 1; i--) {
		dfs(i, i);
	}
	for (int i = 1; i <= n; i++) {
		cout<<dp[i]<<" ";
	}
}
int main() {
	init();
	solve();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> pre[100050];
int dp[100500];
void init() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		pre[b].push_back(a);
	}
}
void dfs(int x, int y) {//仅此处与前处不同
	if (dp[x])	return;//仅此处与前处不同
	dp[x] = max(dp[x], y);
	for (int i = 0; i < pre[x].size(); i++) {
		dfs(pre[x][i], y);
	}
}
void solve() {
	for (int i = n; i >= 1; i--) {
		dfs(i, i);
	}
	for (int i = 1; i <= n; i++) {
		cout<<dp[i]<<" ";
	}
}
int main() {
	init();
	solve();
	return 0;
}

这两份代码的唯一区别就是一个的dfs有返回值而另一个没有,然鹅如果将有返回值的那份代码喂给评测姬则会直接全RE爆0, 但是没有返回值的却完美AC 实在疑惑,求大佬们解答QAQ

2024/8/2 20:50
加载中...