图的存储

链式前向星

• Laoj P1367 图的存储—链式前向星

class graph{
    int h[N];

    struct{
        int t,p,w;
    }e[M];

    public:

    void add_one(int x, int y, int w){
        static int c;
        e[++c]={y,h[x],w}, h[x]=c;
    }

    void add(int x, int y, int w){
        add_one(x,y,w), add_one(y,x,w);
    }

    void dfs(int x){
        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            /* 操作 */
        }
    }
};

树上问题

树的直径

两次 DFS

• SP1437 PT07Z - Longest path in a tree

class graph{
    int mx,p,d[N],f[N];

    public:

    void dfs(int x, int fa){
        if(d[x]>mx) mx=d[x], p=x;

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y!=fa) d[y]=d[x]+1, f[y]=x, dfs(y,x);
        }
    }

    int dia(){
        dfs(1,0), mx=d[p]=0, dfs(p,0);
        return d[p];
    }
};

树形 DP

• Laoj P2236 [模板]树的最长路径

int n;

class graph{
    public:

    void dfs(int x, int f){
        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y==f) continue;

            dfs(y,x);
            if(dp[y][0]+e[i].w>dp[x][0]) dp[x][1]=dp[x][0], dp[x][0]=dp[y][0]+e[i].w;
            else dp[x][1]=max(dp[x][1],dp[y][0]+e[i].w);
        }
    }

    int dia(){
        dfs(1,0);

        int mx=0;
        for(int i=1;i<=n;i++) mx=max(mx,dp[i][0]+dp[i][1]);
        return mx;
    }
};

最近公共祖先

• P3379 【模板】最近公共祖先（LCA）

倍增算法

class graph{
    int d[N],f[N][L];

    public:

    void dfs(int x, int fa){
        d[x]=d[fa]+1, f[x][0]=fa;
        for(int i=1; 1<<i<=d[x]; i++) f[x][i]=f[f[x][i-1]][i-1];

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y!=fa) dfs(y,x);
        }
    }

    int lca(int x, int y){
        if(d[x]<d[y]) swap(x,y);

        for(int i=log2(d[x]); ~i; i--){
            if(d[x]-d[y]>=1<<i) x=f[x][i];
        }
        if(x==y) return x;

        for(int i=log2(d[x]); ~i; i--){
            if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
        }
        return f[x][0];
    }
};

树链剖分

class graph{
    int mx[N],f[N],d[N],t[N];

    void dfs1(int x, int fa){
        static int s[N];
        f[x]=fa, d[x]=d[fa]+1, s[x]=1;

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y==fa) continue;

            dfs1(y,x), s[x]+=s[y];
            if(s[y]>s[mx[x]]) mx[x]=y;
        }
    }

    void dfs2(int x, int p){
        static int c,dfn[N];
        dfn[x]=++c, t[x]=p;
        if(!mx[x]) return;
        dfs2(mx[x],p);

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y!=f[x] && y!=mx[x]) dfs2(y,y);
        }
    }

    public:

    void init(int x){
        dfs1(x,0), dfs2(x,0);
    }

    int lca(int x, int y){
        while(t[x]!=t[y]){
            if(d[t[x]]>d[t[y]]) x=f[t[x]];
            else y=f[t[y]];
        }
        return d[x]<d[y] ? x : y;
    }
};

树的重心

• Laoj P1833 [模板]树的重心

const int INF=0x3f3f3f3f;

int n,dp[N];

class graph{
    public:

    void dfs(int x, int f){
        static int s[N];
        s[x]=1;

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y!=f) dfs(y,x), s[x]+=s[y], dp[x]=max(dp[x],s[y]);
        }
        dp[x]=max(dp[x],n-s[x]);
    }
};

树链剖分

• P3384 【模板】轻重链剖分/树链剖分

int n,MOD,w0[N],w[N];
seg a;

class graph{
    int mx[N],f[N],d[N],s[N],t[N],dfn[N];

    void dfs1(int x, int fa){
        f[x]=fa, d[x]=d[fa]+1, s[x]=1;

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y==fa) continue;

            dfs1(y,x), s[x]+=s[y];
            if(s[y]>s[mx[x]]) mx[x]=y;
        }
    }

    void dfs2(int x, int p){
        static int c;
        dfn[x]=++c, w[c]=w0[x], t[x]=p;
        if(!mx[x]) return;
        dfs2(mx[x],p);

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(y!=f[x] && y!=mx[x]) dfs2(y,y);
        }
    }

    public:

    void init(int x){
        dfs1(x,0), dfs2(x,0), a.build(1,1,n);
    }

    void update(int x, int y, long long w){
        while(t[x]!=t[y]){
            if(d[t[x]]<d[t[y]]) swap(x,y);
            a.update(1,dfn[t[x]],dfn[x],w), x=f[t[x]];
        }

        if(d[x]<d[y]) swap(x,y);
        a.update(1,dfn[y],dfn[x],w);
    }

    long long query(int x, int y){
        long long sum=0;
        while(t[x]!=t[y]){
            if(d[t[x]]<d[t[y]]) swap(x,y);
            sum=(sum+a.query(1,dfn[t[x]],dfn[x]))%MOD, x=f[t[x]];
        }

        if(d[x]<d[y]) swap(x,y);
        return (sum+a.query(1,dfn[y],dfn[x]))%MOD;
    }

    void update(int x, long long w){
        a.update(1,dfn[x],dfn[x]+s[x]-1,w);
    }

    long long query(int x){
        return a.query(1,dfn[x],dfn[x]+s[x]-1);
    }
};

换根

• Laoj P1453 树链剖分

class graph{
    public:

    int r;

    void update(int x, long long w){
        if(dfn[x]+s[x]-1>=dfn[r] && dfn[x]<dfn[r]){
            a.update(1,1,n,w);

            int y=r;
            while(x!=f[y]) y=f[y];
            a.update(1,dfn[y],dfn[y]+s[y]-1,-w);
        }
        else if(x==r) a.update(1,1,n,w);
        else a.update(1,dfn[x],dfn[x]+s[x]-1,w);
    }

    long long query(int x){
        if(dfn[x]+s[x]-1>=dfn[r] && dfn[x]<dfn[r]){
            long long sum=a.query(1,1,n);

            int y=r;
            while(x!=f[y]) y=f[y];
            return sum-a.query(1,dfn[y],dfn[y]+s[y]-1);
        }
        else if(x==r) return a.query(1,1,n);
        else return a.query(1,dfn[x],dfn[x]+s[x]-1);
    }
};

最小生成树

• P3366 【模板】最小生成树

int n,m;

struct node{
    int x,y,w;

    bool operator <(const node x) const{
        return w<x.w;
    }
}e[M];

mfs f;

int mst(){
    f.init(n), sort(e+1,e+m+1);

    int c=0, s=0;
    for(int i=1; i<=m; i++){
        if(!f.merge(e[i].x,e[i].y)) continue;

        s+=e[i].w;
        if(++c==n-1) return s;
    }
    return -1;
}

最短路

Floyd 算法

• B3647 Floyd 算法

const int INF=0x3f3f3f3f;

int n,d[N][N];

void init(){
    memset(d,INF,sizeof d);
    for(int i=1; i<=n; i++) d[i][i]=0;
}

void dis(){
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}

Bellman-Ford 算法

队列优化：SPFA

• P3371 【模板】单源最短路径（弱化版）

const int INF=0x3f3f3f3f;

int d[N];

class graph{
    public:

    void dis(int s){
        bool u[N]={};
        queue<int> q;
        memset(d,INF,sizeof d), d[s]=0, q.push(s);

        do{
            int x=q.front();
            q.pop();
            u[x]=0;

            for(int i=h[x]; i; i=e[i].p){
                int y=e[i].t;
                if(d[x]+e[i].w<d[y]){
                    d[y]=d[x]+e[i].w;
                    if(!u[y]) u[y]=1, q.push(y);
                }
            }
        }while(!q.empty());
    }
};

负环

• P3385 【模板】负环

const int INF=0x3f3f3f3f;

class graph{
    public:

    bool dis(int s){
        int d[N]={},c[N]={};
        bool u[N]={};
        queue<int> q;
        memset(d,INF,sizeof d), d[s]=0, q.push(s);

        do{
            int x=q.front();
            q.pop();
            u[x]=0;

            for(int i=h[x]; i; i=e[i].p){
                int y=e[i].t;
                if(d[x]+e[i].w<d[y]){
                    d[y]=d[x]+e[i].w;
                    if((c[y]=c[x]+1)>=n) return 1;
                    if(!u[y]) u[y]=1, q.push(y);
                }
            }
        }while(!q.empty());

        return 0;
    }
};

Dijkstra 算法

• P4779 【模板】单源最短路径（标准版）

typedef pair<int,int> node;
#define d first
#define p second

const int INF=0x3f3f3f3f;

int d[N];

class graph{
    public:

    void dis(int s){
        bool u[N]={};
        priority_queue<node,vector<node>,greater<node>> q;
        memset(d,INF,sizeof d), d[s]=0, q.push({0,s});

        do{
            int x=q.top().p;
            q.pop();
            if(u[x]) continue;
            u[x]=1;

            for(int i=h[x]; i; i=e[i].p){
                int y=e[i].t;
                if(!u[y] && d[x]+e[i].w<d[y]) q.push({d[y]=d[x]+e[i].w,y});
            }
        }while(!q.empty());
    }
};

连通性相关

强连通分量

• B3609 [图论与代数结构 701] 强连通分量

int n,p,c[N];
vector<int> v[N];

class graph{
    int dfn[N];

    public:

    void tarjan(int x){
        static int d,low[N];
        static bool u[N];
        static stack<int> s;
        dfn[x]=low[x]=++d, u[x]=1, s.push(x);

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(!dfn[y]) tarjan(y), low[x]=min(low[x],low[y]);
            else if(u[y]) low[x]=min(low[x],dfn[y]);
        }

        if(dfn[x]==low[x]){
            c[x]=++p, v[p].push_back(x), u[x]=0;
            while(s.top()!=x){
                int y=s.top();
                s.pop();
                c[y]=p, v[p].push_back(y), u[y]=0;
            }
            s.pop();
        }
    }

    void scc(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i);
        }
    }
};

缩点

• P3387 【模板】缩点

int n,p,a[N],d[N];

class graph{
    static int dfn[N],c[N],w[N];

    public:

    void tarjan(int x){
        static int d,low[N];
        static bool u[N];
        static stack<int> s;
        dfn[x]=low[x]=++d, u[x]=1, s.push(x);

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(!dfn[y]) tarjan(y), low[x]=min(low[x],low[y]);
            else if(u[y]) low[x]=min(low[x],dfn[y]);
        }

        if(dfn[x]==low[x]){
            c[x]=++p, w[p]=a[x], u[x]=0;
            while(s.top()!=x){
                int y=s.top();
                s.pop();
                c[y]=p, w[p]+=a[y], u[y]=0;
            }
            s.pop();
        }
    }

    void scc(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i);
        }
    }

    void rebuild(int x, graph &g){
        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(c[x]!=c[y]) g.add(c[x],c[y]);
        }
    }

    void topo(int x){
        d[x]+=w[x];
        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            d[y]=max(d[y],d[x]);
        }
    }
};

int graph::dfn[N],graph::c[N],graph::w[N];

双连通分量

点双连通分量

• P8435 【模板】点双连通分量

int n,p;
vector<int> v[N];

class graph{
    int dfn[N];

    public:

    void tarjan(int x, int f){
        static int d,low[N];
        static stack<int> s;
        dfn[x]=low[x]=++d, s.push(x);

        if(!f && !h[x]){
            v[++p].push_back(x);
            return;
        }

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(!dfn[y]){
                tarjan(y,x), low[x]=min(low[x],low[y]);
                if(low[y]<dfn[x]) continue;

                v[++p].push_back(x), v[p].push_back(y);
                while(s.top()!=y){
                    int z=s.top();
                    s.pop();
                    v[p].push_back(z);
                }
                s.pop();
            }
            else if(y!=f) low[x]=min(low[x],dfn[y]);
        }
    }

    void pbcc(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i,0);
        }
    }
};

边双连通分量

• P8436 【模板】边双连通分量

int n,p;
vector<int> v[N];

class graph{
    int dfn[N];

    void add_one(int x, int y, int w){
        static int c=1;
        e[++c]={y,h[x],w}, h[x]=c;
    }

    public:

    void tarjan(int x){
        static int d,low[N];
        static bool u[M];
        static stack<int> s;
        dfn[x]=low[x]=++d, s.push(x);

        for(int i=h[x]; i; i=e[i].p){
            if(u[i]) continue;
            u[i]=u[i^1]=1;

            int y=e[i].t;
            if(!dfn[y]) tarjan(y), low[x]=min(low[x],low[y]);
            else low[x]=min(low[x],dfn[y]);
        }

        if(dfn[x]==low[x]){
            v[++p].push_back(x);
            while(s.top()!=x){
                int y=s.top();
                s.pop();
                v[p].push_back(y);
            }
            s.pop();
        }
    }

    void ebcc(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i);
        }
    }
};

割点和桥

割点

• P3388 【模板】割点（割顶）

int n;
bool u[N];

class graph{
    int dfn[N];

    public:

    void tarjan(int x, int f){
        static int d,low[N];
        dfn[x]=low[x]=++d;

        int c=0;
        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(!dfn[y]){
                tarjan(y,x), low[x]=min(low[x],low[y]);
                if(!f) c++;
                else if(low[y]>=dfn[x]) u[x]=1;
            }
            else if(y!=f) low[x]=min(low[x],dfn[y]);
        }
        if(!f && c>1) u[x]=1;
    }

    void cut(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i,0);
        }
    }
};

桥

• P1656 炸铁路

typedef pair<int,int> edge;
#define x first
#define y second

int n,c;
edge a[N];

class graph{
    int dfn[N];

    public:

    void tarjan(int x){
        static int d,low[N],f[N];
        dfn[x]=low[x]=++d;

        for(int i=h[x]; i; i=e[i].p){
            int y=e[i].t;
            if(!dfn[y]){
                f[y]=x, tarjan(y), low[x]=min(low[x],low[y]);
                if(low[y]>dfn[x]) a[++c]={x,y};
            }
            else if(y!=f[x]) low[x]=min(low[x],dfn[y]);
        }
    }

    void bri(){
        for(int i=1; i<=n; i++){
            if(!dfn[i]) tarjan(i);
        }
    }
};

2-SAT

• P4782 【模板】2-SAT 问题

class graph{
    public:

    void scc(){
        for(int i=1; i<=n<<1; i++){
            if(!dfn[i]) tarjan(i);
        }
    }
}g;

int main(){
    while(m--){
        int i,a,j,b;
        scanf("%d%d%d%d",&i,&a,&j,&b);
        g.add(i+n*!a,j+n*b),g.add(j+n*!b,i+n*a);
    }

    g.scc(i);

    for(int i=1; i<=n; i++){
        if(c[i]==c[i+n]){
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for(int i=1; i<=n; i++) printf("%d ",c[i]>c[i+n]);
}

网络流

最大流

• P3376 【模板】网络最大流

const int INF=0x3f3f3f3f;

class graph{
    int d[N];

    void add_one(int x, int y, int w){
        static int c=1;
        e[++c]={y,h[x],w}, h[x]=c;
    }

    bool bfs(int s, int t){
        queue<int> q;
        memset(d,0,sizeof d), d[s]=1, q.push(s);

        do{
            int x=q.front();
            q.pop();
            for(int i=h[x]; i; i=e[i].p){
                int y=e[i].t;
                if(!d[y] && e[i].w) d[y]=d[x]+1, q.push(y);
            }
        }while(!q.empty());

        return d[t];
    }

    int dfs(int x, int t, int l){
        if(x==t) return l;

        int c=0;
        for(int i=h[x]; i && c<l; i=e[i].p){
            int y=e[i].t;
            if(d[y]==d[x]+1 && e[i].w){
                int s=dfs(y,t,min(e[i].w,l-c));
                c+=s, e[i].w-=s, e[i^1].w+=s;
            }
        }

        if(!c) d[x]=-1;
        return c;
    }

    public:

    void add(int x, int y, int w){
        add_one(x,y,w), add_one(y,x,0);
    }

    long long dinic(int s, int t){
        long long c=0;
        while(bfs(s,t)) c+=dfs(s,t,INF);
        return c;
    }
};