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)