给定 � 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++ 的代码实现：

相关问题

给定一张包含 � n 个点以及 � m 条边的无向图，点按 1 1 到 � n 进行编号，试求出点 � s 到点 � t 的最短路长度。

有许多算法可以求解两点之间的最短路，其中比较常用的是 Dijkstra 算法和 Floyd-Warshall 算法。

Dijkstra 算法适用于边权为非负数的图，时间复杂度为 O(nlogn)。Floyd-Warshall 算法适用于任意边权的图，时间复杂度为 O(n^3)。

下面是使用 Dijkstra 算法求解两点之间最短路的 C++ 代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<Edge> g[N];
int dist[N];
bool vis[N];

void dijkstra(int s, int n) {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto& e : g[u]) {
            int v = e.v, w = e.w;
            if (!vis[v] && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(Edge(v, w));
        g[v].push_back(Edge(u, w));
    }
    dijkstra(s, n);
    cout << dist[t] << endl;
    return 0;
}

在这个程序中，我们使用了 STL 中的 vector 和 priority_queue 来实现图的存储和 Dijkstra 算法的优先队列。其中，vector g[i] 存储了以 i 为起点的所有边，dist[i] 表示从起点 s 到点 i 的最短路长度，vis[i] 表示点 i 是否已经被访问。

在 dijkstra 函数中，我们首先初始化 dist 数组和 vis 数组。然后将起点 s 加入优先队列，并开始进行循环。每次从队列中取出当前距离起点最近的点 u，并将它标记为已访问。然后遍历 u 的所有邻居点 v，如果 v 还没有被访问，并且从 s 到 u 再到 v 的距离比之前计算的 dist[v] 更短，则更新 dist[v]，并将 v 加入优先队列。

最后输出 dist[t]，即为起点 s 到终点 t 的最短路径长度。

需要注意的是，如果图中存在负边权，不能使用 Dijkstra 算法。此时可以使用 Bellman-Ford 算法或 SPFA 算法来求解最短路。

用c语言写给定一张包含 � n 个点以及 � m 条边的无向图，点按 1 1 到 � n 进行编号，试求出点 � s 到点 � t 的最短路长度。

以下是使用 Dijkstra 算法求解两点之间最短路的 C 代码：

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define N 10000
#define M 100000

typedef struct edge {
    int v;  // 边的终点
    int w;  // 边的权值
    struct edge *next;  // 链表下一条边
} Edge;

Edge edges[M * 2 + 1];  // 边的链表
int head[N + 1];  // 每个点的第一条边
int dist[N + 1];  // 起点到每个点的最短距离
bool vis[N + 1];  // 记录每个点是否已经访问
int heap[N + 1];  // 堆
int heap_size;  // 堆的大小

// 初始化边的链表和每个点的第一条边
void init() {
    for (int i = 0; i <= N; i++) {
        head[i] = -1;
    }
}

// 添加一条边
void add_edge(int u, int v, int w) {
    edges[heap_size].v = v;
    edges[heap_size].w = w;
    edges[heap_size].next = head[u];
    head[u] = heap_size++;
}

// 堆的操作
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heap_push(int x) {
    heap[heap_size++] = x;
    int i = heap_size - 1;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (dist[heap[p]] > dist[x]) {
            heap[i] = heap[p];
            i = p;
        } else {
            break;
        }
    }
    heap[i] = x;
}

int heap_pop() {
    int x = heap[0];
    heap[0] = heap[--heap_size];
    int i = 0, c = 1;
    while (c < heap_size) {
        if (c + 1 < heap_size && dist[heap[c + 1]] < dist[heap[c]]) {
            c++;
        }
        if (dist[heap[c]] < dist[heap[i]]) {
            swap(&heap[c], &heap[i]);
            i = c;
            c = i * 2 + 1;
        } else {
            break;
        }
    }
    return x;
}

// Dijkstra 算法
void dijkstra(int s) {
    // 初始化
    heap_size = 0;
    for (int i = 1; i <= N; i++) {
        dist[i] = INT_MAX;
        vis[i] = false;
    }
    dist[s] = 0;
    heap_push(s);

    // 循环
    while (heap_size > 0) {
        int u = heap_pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].v, w = edges[i].w;
            if (!vis[v] && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                heap_push(v);
            }
        }
    }
}

int main() {
    int n, m, s, t;
    scanf("%d %d %d %d", &n, &m, &s, &t);
    init();
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dijkstra(s);
    printf("%d\n", dist[t]);
    return 0;
}

在这个程序中，我们首先定义了一个结构体Edge，它包含了一条边的终点和边权。然后我们定义了一个数组head，它存储每个点的第一条边。我们使用链表来存储边，每个点的第一条边存储在head数组中，之后的边通过链表的next指针连接起来。

在输入完边后，我们使用add_edge函数来添加边到链表中。由于是无向图，所以每条边需要在两个方向上都添加。

接下来，我们使用Dijkstra算法来求解起点s到终点t的最短路。我们使用一个堆来维护当前距离起点最近的点，堆中存储的是点的编号。堆中的元素按照dist数组的值从小到大排序。在堆的操作中，我们使用自下而上的方式将元素插入堆中，使用自上而下的方式将元素取出堆中。

在dijkstra函数中，我们首先初始化dist数组和vis数组。然后将起点s加入堆中，并开始进行循环。每次从堆中取出当前距离起点最近的点u，并将它标记为已访问。然后遍历u的所有邻居点v，如果v还没有被访问，并且从s到u再到v的距离比之前计算的dist[v]更短，则更新dist[v]，并将v加入堆中。

最后输出dist[t]，即为起点s到终点t的最短路径长度。