1 条题解
-
0
对每个点分别用dfs求出答案即可,时间复杂度。需要注意每次处理新的点之前,需要把标记清空。
参考代码
#include <bits/stdc++.h> using namespace std; int n, m, u, v, ans; vector<int> g[1005]; bool vis[1005];//每个点是否访问过 void dfs(int u) { vis[u] = true; ans = max(ans, u); for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]]) dfs(g[u][i]); } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u >> v; g[u].push_back(v); } for (int i = 1; i <= n; i++) { ans = 0; memset(vis, false, sizeof(vis)); dfs(i); cout << ans << " "; } return 0; }
- 1
信息
- ID
- 895
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 23
- 已通过
- 13
- 上传者