三种邻接表存图模板：vector邻接表、数组邻接表、链式前向星

vector邻接表：

const int maxn=1e5+;

struct Edge{

    int u,v,w;

    Edge(int _u=0,int _v=0,int _w=0){u=_u,v=_v,w=_w;}

};

vector<Edge> E;

vector<int> G[maxn];

void init(int l,int r)

{

    E.clear();

    for(int i=l;i<=r;i++) G[i].clear();

}

void addedge(int u,int v,int w)

{

    E.push_back(Edge(u,v,w));

    G[u].push_back(E.size()-);

}

遍历某个链表的方法： for(int i=;i<G[u].size();i++)

最喜欢这种写法，写起来快，也非常好理解。

vector邻接表还有一种魔性写法：

const int maxn=1e5+;

struct Edge{

    int u,v,w;

    Edge(int u=,int v=,int w=){this->u=u,this->v=v,this->w=w;}

};

vector<Edge> E[maxn];

void init(int l,int r){for(int i=l;i<=r;i++) E[i].clear();}

void addedge(int u,int v,int w){E[u].push_back(Edge(u,v,w));}

其实差不多……属于懒人中的懒人写法。

数组邻接表：

const int maxn=1e5+;

const int maxm=1e5+;

struct Edge{

    int u,v,w;

    Edge(int _u=,int _v=,int _w=){u=_u,v=_v,w=_w;}

    Edge(Edge &e){u=e.u,v=e.v,w=e.w;}

};

Edge E[maxm];

int head[maxn],next[maxm],ne;

void init()

{

    ne=;

    memset(head,,sizeof(head));

}

void addedge(int u,int v,int w)

{

    E[++ne]=Edge(u,v,w);

    next[ne]=head[u];

    head[u]=ne;

}

遍历某个链表的方法： for(int i=head[u];i;i=next[i])

在题目卡vector时可以使用，如果include了STL库，可能next数组会产生ambiguous，需要改个名字或者改用链式前向星（如下）。

链式前向星：

const int maxn=1e5+;

const int maxm=1e5+;

struct Edge{

    int u,v,w;

    int next;

};

Edge E[maxm];

int head[maxn],ne;

void init()

{

    ne=;

    memset(head,,sizeof(head));

}

void addedge(int u,int v,int w)

{

    ++ne;

    E[ne].u=u, E[ne].v=v, E[ne].w=w;

    E[ne].next=head[u];

    head[u]=ne;

}

把数组邻接表的next数组扔到Edge结构体里保存，就变成了链式前向星……所以，链式前向星其实就是邻接表。

遍历某个链表的方法： for(int i=head[u];i;i=E[i].next)