众所周知,最典型的邻接表是用头插法实现的,其代码精简和效果让人震撼。

但是我们有时候因为某些限制条件必须用到尾插法来处理一些优先关系,然而百度上怎么也找不到 可能都觉得太简单了吧 这里本菜鸡就贴一个个人的邻接表尾插法实现。

const int maxn = 1010;

int idx;
int head[maxn], tail[maxn];

struct node {
    int to;
    int nxt;
} edges[maxn * 10];

void addEdge(int u, int v) //核心在这里
{
    if (head[u] == -1)
        head[u] = idx;
    if (tail[u] != -1)
        edges[tail[u]].nxt = idx;
    edges[idx].to = v;
    edges[idx].nxt = -1;
    tail[u] = idx++;
}

void init()
{
    memset(head, -1, sizeof head);
    memset(tail, -1, sizeof tail);
}

如果你学过链表,这份代码是很容易理解的……我就不多说了。
遍历方式和尾插法一致 是 for(int u=head[u];~u;u=edges[u].nxt) ;

这个代码比经典的头插法邻接表多了 O(n) 的空间,还有两个判断语句,在空间和时间上都比不上头插法邻接表。but who cares?

另外尾插法邻接表也可直接考虑用 vector 向量写,写起来方便些。