用邻接表构建一个有向图，输入格式：第一行有2个整数n,m。 接下来m行，每行2个整数ui​,vi​,表示ui​到vi​有一条边C++实现

下面是基于邻接表的有向图的C++实现：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    // 输出邻接表
    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        for (int j = 0; j < graph[i].size(); j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

输入格式为：第一行输入两个整数n和m，分别表示有向图的节点数和边数。接下来m行每行两个整数u和v，表示从u到v有一条边。

输出结果为邻接表，其中第i行表示节点i的出边列表。例如，第0行的输出表示节点0的出边列表。

相关问题

给定n个点，m条边的有向图，对于每个点v，求f(v)表示从点v出发能到达的编号最大的点(包括自己在内)。 n≤10^5,m≤10^5输入格式：第一行有2个整数n,m。 接下来m行，每行2个整数ui​,vi​,表示ui​到vi​有一条边。 点用1,2,⋯,n编号。输出形式：n个整数

可以使用深度优先搜索（DFS）来解决该问题。对于每个点v，进行一次DFS，记录能够到达的最大编号max_id。最后输出每个点的max_id即可。

具体实现时，可以使用一个数组visited来记录每个点是否已经被访问过，避免重复访问。同时，需要记录当前DFS路径上的最大编号，以便更新max_id。

以下是代码实现：

n, m = map(int, input().split())

# 构建邻接表
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)

# DFS函数
def dfs(v, visited, max_id):
    visited[v] = True
    max_id = max(max_id, v)
    for w in graph[v]:
        if not visited[w]:
            max_id = max(max_id, dfs(w, visited, max_id))
    return max_id

# 对每个点进行DFS
for i in range(n):
    visited = [False] * n
    max_id = dfs(i, visited, i)
    print(max_id+1, end=' ')

时间复杂度为O(nm)，空间复杂度为O(n+m)。

求有向图G中各顶点的入度与出度。建议分别采用邻接矩阵和邻接表这两种不同的存储结构完成。 输入格式: 首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试第一行输入2个整数n、m（2≤n≤26，1≤m≤n(n-1)/2），分别表示顶点数、边数；然后输入m行，每行包含两个顶点Ai、Bi（大写字母表示），表示Ai到Bi有一条有向边。 输出格式: 对于每组测试，输出n行，依顶点的字典序在每行上输出各顶点的入度和出度（数据之间留一个空格）。 输入样例: 1 5 4 A C A B B D E C 输出样例: 0 2 1 1 2 0 1 0 0 1

邻接矩阵与邻接表分别求解有向图中各个顶点的入度和出度的方法如下：

邻接矩阵：

1. 构建一个大小为 n*n 的邻接矩阵，其中 n 表示顶点数。

2. 对于每条有向边 (i,j)，将邻接矩阵中第 i 行第 j 列的元素设为 1。

3. 统计每个顶点的入度和出度。对于第 i 个顶点，其入度为第 i 列中非零元素的个数，出度为第 i 行中非零元素的个数。

邻接表：

1. 构建一个大小为 n 的邻接表数组，其中 n 表示顶点数。

2. 对于每条有向边 (i,j)，将顶点 i 的邻接表中加入一个指向 j 的边。

3. 统计每个顶点的入度和出度。对于第 i 个顶点，其入度为所有指向 i 的边的个数，出度为其邻接表的长度。

以下是代码实现：