【模板】链式前向星

xxxasybt2023 · 2025-08-11 18:56:08 · 科技·工程

首选代码块

强势封装无权

struct Graph
{
    static const int N = 1e5+5,M = 2e5+5;
    struct node {int to,ne;} edge[M];
    int head[N],len = 0;
    struct iterator
    {
        int indx;Graph *g;
        iterator (int _i,Graph *_g) : indx(_i) , g(_g) {}
        iterator operator++(int) {iterator t = *this;return indx = g->edge[indx].ne,t;}
        bool operator!=(const iterator& _i) const
        {
            if (_i.g == nullptr) return indx;
            return indx!=_i.indx || g!=_i.g;
        }
        operator int() {return g->edge[indx].to;}
    };
    inline void clear() {memset(head,0,sizeof head),len = 0;}
    inline void insert(int u,int v) {edge[++len] = {v,head[u]},head[u] = len;}
    inline void add(int u,int v) {insert(u,v),insert(v,u);}
    inline iterator begin(int x) {return iterator(head[x],this);}
    inline iterator end() {return iterator(0,nullptr);}
};

极简带权

const int N = 1e6+5;
struct edge {int to,ne,w;} e[N<<1];
int head[N],len;
void insert(int u,int v,int w) {e[++len] = {v,head[u],w},head[u] = len;}

极简无权

const int N = 1e6+5;
struct edge {int to,ne;} e[N<<1];
int head[N],len;
void insert(int u,int v) {e[++len] = {v,head[u]},head[u] = len;}

带权

功能大/码量大

模板封装

template <typename T>
struct LFS
{
    static const int N = 1e5+5,M = 5e5+5;
    struct node {int to,ne;T w;} edge[M];
    struct iterator
    {
        int indx;LFS *g;
        iterator (int _i,LFS *_g) : indx(_i) , g(_g) {}
        iterator operator++(int) {iterator t = *this;return indx = g->edge[indx].ne,t;}
        iterator& operator++() {return indx = g->edge[indx].ne,*this;}
        operator bool () {return (bool)indx;}
        operator int () {return indx;}
    };
    int head[N],len = 0;
    void insert(int u,int v,T w) {edge[++len] = {v,head[u],w},head[u] = len;}
    void add(int u,int v,T w) {insert(u,v,w),insert(v,u,w);}
    iterator begin(int x) {return iterator(head[x],this);}
};

还有

template <typename T>
struct LFS
{
    static const int N = 2e5+5,M = 5e5+5;
    struct node {int to,ne;T w;} edge[M];
    int head[N],len = 0;
    inline void clear() {memset(head,0,sizeof head),len = 0;}
    inline void insert(int u,int v,T w) {edge[++len] = {v,head[u],w},head[u] = len;}
    inline void add(int u,int v,T w) {insert(u,v,w),insert(v,u,w);}
};

int版

struct LFS
{
    static const int N = 1e5+5,M = 2e5+5;
    struct node {int to,ne,w;} edge[M];
    struct iterator
    {
        int indx;LFS *g;
        iterator (int _i,LFS *_g) : indx(_i) , g(_g) {}
        iterator operator++(int) {iterator t = *this;return indx = g->edge[indx].ne,t;}
        iterator& operator++() {return indx = g->edge[indx].ne,*this;}
        operator bool () {return (bool)indx;}
        operator int () {return indx;}
    };
    int head[N],len = 0;
    void insert(int u,int v,int w) {edge[++len] = {v,head[u],w},head[u] = len;}
    void add(int u,int v,int w) {insert(u,v,w),insert(v,u,w);}
    iterator begin(int x) {return iterator(head[x],this);}
};

功能小/码量小

struct LFS
{
    static const int N = 1e5+5,M = 2e5+5;
    struct node {int to,ne,w;} edge[M];
    int head[N],len = 0;
    void insert(int u,int v,int w) {edge[++len] = {v,head[u],w},head[u] = len;}
    void add(int u,int v,int w) {insert(u,v,w),insert(v,u,w);}
};

无权

struct LFS
{
    static const int N = 1e5+5,M = 5e5+5;
    struct node {int to,ne;} edge[M];
    int head[N],len = 0;
    void insert(int u,int v) {edge[++len] = {v,head[u]},head[u] = len;}
    void add(int u,int v) {insert(u,v),insert(v,u);}
};