35 lines
1.5 KiB
C++
35 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
//用链表来代替vector实现邻接表 (用数组来模拟存储链表) 拉链法的HASH表
|
||
const int N = 1010; //结点个数
|
||
int h[N]; //h[N]表示有N条单链表的头
|
||
int e[N << 1]; //e[N<<1]代表每个节点的值 链表记录的是关系
|
||
int ne[N << 1]; //ne[N<<1]代表每个节点的下一个节点号 链表记录的是关系
|
||
int idx; //结点编号
|
||
int w[N << 1]; //边的权值
|
||
//一般认为N<<1就够用了,就是2*N个大小
|
||
|
||
// 添加一条边a->b (头插法),边权值是val
|
||
void add(int a, int b, int val) {//有的时候可以不用建立权值
|
||
e[idx] = b, ne[idx] = h[a], w[idx] = val, h[a] = idx++;
|
||
// https://www.acwing.com/video/21/ yxc老师的讲解头插法
|
||
// ne[idx]=h[a]的意义：将原来h[a]是指向第一个子结点的，现在，记录idx的下一个结点是原来的第一个节点，它现在是第一个了，
|
||
// 原来的第一个是第二个了。
|
||
// h[a]=idx++的意义： a这个结点的第一个子结点是idx了，然后再把 idx增加1个！方便下次加入新结点
|
||
}
|
||
|
||
int main() {
|
||
//给定初始值
|
||
memset(h, -1, sizeof h);
|
||
/* 遍历以u为出发点的链表办法
|
||
for(int i=1;i<=n;i++){ //n个点
|
||
for (int j = h[u]; j != -1; j = ne[j]) {//遍历以i为起点的所有边
|
||
|
||
}
|
||
}
|
||
其实链式前向星也是枚举每个起点的所有边，只不过它是以边进行建图的
|
||
*/
|
||
return 0;
|
||
} |