图论模板

dream_qwq · 2022-11-21 13:04:38 · 算法·理论

这是一篇关于*图论模板*的文章这些是其他模板分类的链接	数据结构	字符串	数学	杂项

图的存储

链式前向星

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](https://www.luogu.com.cn/problem/SP1437)
```cpp
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）](https://www.luogu.com.cn/problem/P3379)
### 倍增算法
```cpp
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 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384)
```cpp
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 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
```cpp
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 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
```cpp
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 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
```cpp
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 【模板】缩点](https://www.luogu.com.cn/problem/P3387)
```cpp
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 【模板】边双连通分量](https://www.luogu.com.cn/problem/P8436)
```cpp
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 炸铁路](https://www.luogu.com.cn/problem/P1656)
```cpp
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+nb),g.add(j+n!b,i+na); }

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 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
```cpp
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;
    }
};