首页给定 n个点， m条边的有向图，对于每个点 v，求从点 v出发能到达的编号最大的点(包括自己在内)。C++实现，不用STL

给定 n个点， m条边的有向图，对于每个点 v，求从点 v出发能到达的编号最大的点(包括自己在内)。C++实现，不用STL

时间: 2024-02-12 21:07:34 浏览: 158

我们可以使用深度优先搜索（DFS）来解决这个问题。首先，我们需要定义一个数组 `vis`，用于记录每个点是否被访问过。然后，对于每个点 v，我们可以从它开始进行 DFS，记录能够到达的最大点编号。具体实现如下： ```c++ const int N = 100005; int n, m; int head[N], nxt[N], to[N], cnt = 0; int maxn[N]; // 记录每个点能到达的最大点编号 bool vis[N]; // 标记数组，记录每个点是否被访问过 void add_edge(int u, int v) { nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v; } void dfs(int u, int &max_id) { vis[u] = true; maxn[u] = u; for (int i = head[u]; i; i = nxt[i]) { int v = to[i]; if (!vis[v]) { dfs(v, max_id); } maxn[u] = max(maxn[u], maxn[v]); } max_id = max(max_id, maxn[u]); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v); } for (int i = 1; i <= n; ++i) { if (!vis[i]) { int max_id = i; dfs(i, max_id); printf("%d\n", max_id); } } return 0; } ``` 在主函数中，我们依次对每个点进行 DFS，记录能够到达的最大点编号，并输出即可。时间复杂度：O(n+m)。

阅读全文