C++，给定一张n个点m条边的有向图，统计有多少点满足：从图上任意点出发，都可以沿图上的有向边到达这个点

称这样的点为"强连通点"，要统计这样的点的个数，就需要使用图的强连通分量的概念。强连通分量指的是一个点集，其中任意两点都是强连通的，也就是说可以从任意一个点出发到达其他任意点。强连通分量的点的个数就是答案。

C 语言中，可以使用 tarjan 算法或者 kosaraju 算法来求解图的强连通分量。具体实现细节可以参考一些数据结构与算法的学习资料。

相关问题

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

我们可以使用深度优先搜索（DFS）来解决这个问题。

首先，我们需要定义一个数组 `vis`，用于记录每个点是否被访问过。然后，对于每个点 v，我们可以从它开始进行 DFS，记录能够到达的最大点编号。具体实现如下：

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)。

用c++写出有一个n 个点 m 条边的无向图，请求出从 s 到 t 的最短路长度代码

以下是使用 Dijkstra 算法求解最短路的 C++ 代码实现：

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

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, s, t;
vector<pair<int, int>> adj[MAXN];
int dist[MAXN];
bool vis[MAXN];

void dijkstra(int s) {
    memset(dist, INF, 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(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

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

其中 adj[] 存储了邻接表，dist[] 存储了起点到每个点的最短距离，vis[] 表示该点是否已经被访问过。优先队列 pq 存储了 (dis, u)，表示起点到 u 的距离为 dis。在 dijkstra 函数中，先将起点 s 的距离设为 0，其余点的距离设为正无穷。然后将起点 s 加入队列 pq，当队列不为空时，取出队首元素 (dis, u)，如果 u 的距离已经被更新，直接跳过。否则，更新 u 的距离为 dis，并遍历 u 的所有邻接点 v，如果起点到 v 的距离可以被更新，将 (dis+cost(u, v), v) 加入队列 pq。最终返回 dist[t]，即为起点到 t 的最短路长度。