一点小思绪

目录

• 前言
• 编号
  • 有向图
  • 无向图
• 通常是什么样的访问？
  • 点访问与其相邻的边
  • 边访问与其相邻的点
  • 通常的边的信息？
• 更高级的访问：边与点相关的信息
  • 有向图
  • 无向图（本博文重点）

前言

如何更方便地操作边？

都知道异或对偶， 即 2^1=3, 3^1=2， 也就是对于偶数 x， x^1=x+1， 对于奇数 y， y^1=y-1， 这样就可以在邻接表中把某条边的反向边紧密地联系在一起。（用于无向图判一条边）

今天肤浅地考虑了下 CSP-S2019 树上的数， 觉得在使用邻接表的前提下， 应该能有一套如邻接表一样可以直接打出来的板子， 使得可以对边更方便地操作。

编号

有向图

有向图不用考虑在邻接表中不同标号的边实际上在逻辑意义上是一条边的问题， 那么就可以直接用邻接表的标号。

无向图

无向图要给边重新编号

通常是什么样的访问？

点访问与其相邻的边

这个邻接表就可以做到。

边访问与其相邻的点

点的标号是不相同的， 这个就随便做了

通常的边的信息？

在邻接表里加一堆卫星数据就行了

更高级的访问：边与点相关的信息

有向图

记录 from 即可

无向图（本博文重点）

给边单独开结构体， 记录相邻点， 同时储存数据。

struct Es{
	int p[2];
    int info[2];
    void iN(int x,int y) {
        p[0]=x, p[1]=y;
        if(p[0]>p[1]) swap(p[0],p[1]);
        info[0] = info[1] = 0;
	}
    int id(int x) {return x==p[1];} //判断 x 是 p[0] 还是 p[1]
}