51 lines
1.5 KiB
C++
51 lines
1.5 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
const int N = 10010, M = N << 1; // 最大顶点数,最大边数
|
|||
|
|
|
|||
|
|
/*
|
|||
|
|
链式前向星:保存的是每一个顶点的所有出边
|
|||
|
|
|
|||
|
|
h[u] 表示点u为出发点的第一条边的编号
|
|||
|
|
e[i] 表示第i条边的指向终点,有时也写作to[i]
|
|||
|
|
ne[i] 表示第i条边的下一条边的编号
|
|||
|
|
idx 记录边的数量，表现在代码中就是一个计数器
|
|||
|
|
*/
|
|||
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|||
|
|
|
|||
|
|
// 添加一条从 a 到 b 的边,边权为c
|
|||
|
|
void add(int a, int b, int c = 0) {
|
|||
|
|
// e[idx]=b 第idx号边，是指向点b的
|
|||
|
|
// ne[idx]=h[a] 第idx号边，它的下一条边是原来h[a]指向的边
|
|||
|
|
// w[idx]=c 第idx号边，权值是c
|
|||
|
|
// h[a]=idx++ 以a点为出发点的所有边组成的链表中，第一个是idx号边,头插法
|
|||
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
// 初始化
|
|||
|
|
memset(h, -1, sizeof h);
|
|||
|
|
|
|||
|
|
int n = 5; // 顶点数
|
|||
|
|
// 添加边
|
|||
|
|
add(0, 1);
|
|||
|
|
add(0, 2);
|
|||
|
|
add(1, 3);
|
|||
|
|
add(2, 3);
|
|||
|
|
add(3, 4);
|
|||
|
|
|
|||
|
|
// 遍历从每个顶点出发的边
|
|||
|
|
for (int u = 0; u < n; u++) {
|
|||
|
|
// cout << "从 " << u << "号节点引出的边: " << endl;
|
|||
|
|
|
|||
|
|
for (int i = h[u]; ~i; i = ne[i]) { // 枚举从点u出发的每条边
|
|||
|
|
int v = e[i];
|
|||
|
|
// u 到点 v 的边
|
|||
|
|
cout << u << " -> " << v << endl;
|
|||
|
|
}
|
|||
|
|
cout << endl;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return 0;
|
|||
|
|
}
|