使用邻接表, 构建有向无权图
const int N;
int h[N], e[N], ne[N], idx;
void add(int a, int b){
/*
函数使用的是头插法构建邻接表
数据说明:
idx就是节点
e[idx]存储节点元素的值
ne[idx]存储下一个节点的指针
h[a] 相对于b来说 a 是头结点,因为a -> b
逻辑:
申请一个节点并赋值,采用头插法,该节点的指向下一个节点的指针等于头结点保存的下一个节点的指针,头结点指向该节点,节点数++
*/
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
每次在遍历一个节点的所有子节点时,可以通过
for(int i = h[u]; ~i; i = ne[i])
这里的~i是因为c++是用补码存储二进制,-1的二进制全是1,取反后二进制的十进制表示就是0