给定 � n个点， � m条边的有向图，对于每个点 � v，求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行，每行2个整数 � � , � � u i ​ ,v i ​ ,表示 � � u i ​ 到 � � v i ​ 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format数据结构c++

可以使用拓扑排序和动态规划来解决这个问题。

首先进行一次拓扑排序，得到每个点的入度和出度，并将入度为 0 的点加入队列中。

接下来进入动态规划阶段，每次从队列中取出一个入度为 0 的点，将其与其后继节点进行比较，如果后继节点的 f 值比当前节点大，则更新后继节点的 f 值。

在更新后继节点的 f 值后，若后继节点的入度为 0，则将其加入队列中。

直到队列为空，所有节点的 f 值都已经计算出来了。

以下是 C++ 的代码实现：

相关问题

用数据结构c++处理：给定 � n个点， � m条边的有向图，对于每个点 � v，求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行，每行2个整数 � � , � � u i ​ ,v i ​ ,表示 � � u i ​ 到 � � v i ​ 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format数据结构c++

可以使用邻接表来存储有向图，然后对于每个点，进行一次DFS或BFS遍历，记录能够到达的最大编号的点。

具体实现可以参考以下代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 5;

vector<int> adj[MAXN];
int n, m;
bool visited[MAXN];

// DFS遍历
int dfs(int v) {
    int res = v;
    visited[v] = true;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            int tmp = dfs(u);
            if (res < tmp) res = tmp;
        }
    }
    return res;
}

// BFS遍历
int bfs(int v) {
    int res = v;
    queue<int> q;
    q.push(v);
    visited[v] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++) {
            int w = adj[u][i];
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
                if (res < w) res = w;
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int v = 1; v <= n; v++) {
        // 初始化visited数组
        for (int i = 1; i <= n; i++) visited[i] = false;
        // DFS或BFS遍历
        int max_id = dfs(v); // or bfs(v)
        cout << max_id << endl;
    }
    return 0;
}