王码编程 OJ 首页 问题列表 比赛 社团 排行榜 记录 新闻通知 课程 帮助 暂无头像 赵怡豪 ×提交成功 2606 - 图的遍历 通过次数

33

提交次数

57

旧版界面 时间限制 : 1 秒 内存限制 : 512 MB 给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v)表示从点 v 出发，能到达的编号最大的点。

输入 第1行2个整数N,M，表示点数和边数。 接下来M行，每行2个整数,Ui ,Vi表示边(Ui,Vi)。点用 1,2,…,N 编号。 对于60%的数据，1≤ N，M≤1000 对于100%的数据，1≤N，M≤100000

输出 一行N个整数A(1),A(2)......A(N)。

样例 输入复制 4 3 1 2 2 4 4 3 输出复制 4 4 3 4

C++ 1 ​ 刚刚 Accepted × 提交时间：2024-07-15 16:11:40

运行 ID: 218005

include <bits/stdc++.h>

define M 100005

using namespace std; int vis[M], ans[M]; vector G[M]; int n, m; void dfs(int v, int max) {

vis[v] = 1;
ans[v] = max;
for (auto k : G[v]) {
	if (vis[k] == 0) {
		dfs(k, max);
	}
}

}

int main() {

cin >> n >> m;
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= m; i++) {
	int u, v;
	cin >> u >> v;
	G[v].push_back(u);
}
for (int i = n; i > 0; i--) {
	if (vis[i] == 0) {
		dfs(i, i);
	}
}
for (int i = 1; i <= n; i++) {
	cout << ans[i] << " ";
}
return 0;

}

© 2019 - 2024王码编程  滇ICP备19007937号-1如果您有任何问题，请联系我们 YNOIer@163.com您是本系统的第位访问者