欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论模板

程序员文章站 2022-05-22 14:56:16
...

图论模板

LCA

离线

tarjan

//可使用快读
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=500050;
int po[MAXN],qs[MAXN],fa[MAXN],nume,numq,n,m,root,ans[MAXN];
bool f[MAXN];
struct edge{
    int to,nxt;
}e[2*MAXN];
struct ques{
    int to,nxt,num;
}q[2*MAXN];
void adde(int from,int to){
    e[++nume].nxt=po[from];
    e[nume].to=to;
    po[from]=nume;
}
void addq(int from,int to,int num){
    q[++numq].nxt=qs[from];
    q[numq].to=to;
    q[numq].num=num;
    qs[from]=numq;
}
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y){
    int r1=find(x),r2=find(y);
    if(r1!=r2){
        fa[r1]=r2;
    }
}
void tarjan(int u){
    f[u]=1;
    for(int i=qs[u];i;i=q[i].nxt){
        int v=q[i].to;
        if(f[v]) ans[q[i].num]=find(v);
    }
    for(int i=po[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!f[v]) {   //此处是v不是i
            tarjan(v);merge(v,u);
        }
    }
}
int main(){
//  freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    for(int i=1;i<=n;i++) fa[i]=i;//记得初始化
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addq(u,v,i);addq(v,u,i);
    }
    tarjan(root);
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
//  fclose(stdin);
    return 0;
}

洛谷P3379

在线

倍增

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=500005;
int head[MAXN],nume,n,m,root,dep[MAXN],ind,tin[MAXN],tout[MAXN],fa[MAXN][21];
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
struct edge{
    int to,nxt;
}e[MAXN<<1];
void adde(int from,int to){
    e[++nume].to=to;
    e[nume].nxt=head[from];
    head[from]=nume;
}
void dfs(int u,int rt,int k){
    tin[u]=++ind;
    dep[u]=k;
    fa[u][0]=rt;
    for(int i=1;(1<<i)<=(n/2);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=rt) dfs(v,u,k+1);
    }
    tout[u]=++ind;
}
bool chk(int a,int b){
    if(tin[a]<=tin[b]&&tout[a]>=tout[b]) return 1;
    else return 0;
}
int LCA(int x,int y){   
    if(chk(x,y)) return x;
    if(chk(y,x)) return y;
    if(dep[x]>dep[y]) swap(x,y);
    for(int i=log2(dep[x]+1);i>=0;i--){
        if(!chk(fa[x][i],y)){
            x=fa[x][i];
        }
    }   
    return fa[x][0];
}
int main(){
    n=init();m=init();root=init();
    for(int i=1;i<n;i++){
        int u=init(),v=init();
        adde(u,v);adde(v,u);
    }
    dfs(root,root,1);
    //for(int i=1;i<=n;i++) printf("%d ",fa[i][1]);
    for(int i=1;i<=m;i++){
        int u=init(),v=init();
        printf("%d\n",LCA(u,v));
    }
    return 0;
}

最短路径

dijkstra

稠密图就用它
朴素的dijkstra的时间复杂度是O(N^2),对于数据量大的,一般过不了。
STL堆优化dijkstra O(M*logN),网上的博客对时间复杂度的分析大都是错的,使用方便,较优,一般可以使用。
由于每次松弛操作都要进队列,导致时间复杂度偏高。

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=10005,MAXM=500005;
int head[MAXN],nume,n,m,start,dis[MAXN];
struct edge{
    int to,nxt,dis;
}e[MAXM];//如果是无向边 就要开两倍数组大小。
void adde(int from,int to,int dis){
    e[++nume].to=to;
    e[nume].nxt=head[from];
    e[nume].dis=dis;
    head[from]=nume;
}
int read(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            fh=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return rv*fh;//记得返回值
}
struct cmp{
    bool operator() (const int &a,const int &b) const{
        return dis[a]>dis[b];
    }
}; //     ATTENTION!!!!
int main(){
    freopen("in.txt","r",stdin);
    n=read();m=read();start=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),dis=read();
        adde(u,v,dis);
    }
    for(int i=1;i<=n;i++) dis[i]=0x7fffffff/3;
    dis[start]=0;
    priority_queue <int,vector<int>,cmp >he;
    he.push(start);
    while(!he.empty()){
        int u=he.top();
        he.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis){
                dis[v]=dis[u]+e[i].dis;
                he.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==0x7fffffff/3) printf("%d ",0x7fffffff);
        else printf("%d ",dis[i]);
    }
    fclose(stdin);
    return 0;
}

上文中的代码中应用了STL的priority_queue,此数据结构以堆的形式实现优先队列,默认大根堆,比较符号为小于号,即less< int >,
可使用greater< int >变成小根堆。但在定义的时候
priority_queue <(空格) < int>,vector< int >,greater< int >(空格)>
也可重载小于号.
也可定义一个比较类,如上文,注意重载(),且a < b时为大根堆。

手写堆优化dijkstra
clever

SPFA

稀疏图使用
O(kE) 不稳定可能退化成O(n^3)可以判负权回路
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=10005,MAXM=500005;
int head[MAXN],n,m,start,dis[MAXN],nume;
struct edge{
    int to,nxt,dis;
}e[MAXM];
queue <int> spfa;
bool f[MAXN];
int read(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            fh=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
void adde(int from,int to,int dis){
    e[++nume].to=to;
    e[nume].dis=dis;
    e[nume].nxt=head[from];
    head[from]=nume;
}

int main(){
    freopen("in.txt","r",stdin);
    n=read();m=read();start=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),dis=read();
        adde(u,v,dis);/*adde(v,u,dis);*/
    }
    for(int i=1;i<=n;i++) dis[i]=0x7fffffff/3;
    dis[start]=0;
    f[start]=1;
    spfa.push(start);
    while(!spfa.empty()){
        int u=spfa.front();
        spfa.pop();
        f[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis){
                dis[v]=dis[u]+e[i].dis;
                if(!f[v]){
                    f[v]=1;
                    spfa.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==0x7fffffff/3) printf("%d ",0x7fffffff);
        else printf("%d ",dis[i]);
    }
    fclose(stdin);
    return 0;
}

最小生成树

kruskal
O(E*logE) 稀疏图较好,代码简单。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct edge{
    int from,to,dis;
}e[400005];
int fa[5005],n,m,nume,k,tot;
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y){
    int r1=find(x),r2=find(y);
    if(r1!=r2) fa[r1]=r2;
}
bool cmp(edge a,edge b){
    return a.dis<b.dis;
}
int read(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return rv*fh;
}
int main(){
    freopen("in.txt","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),dis=read();
        e[++nume].from=u;e[nume].to=v;e[nume].dis=dis;
    }
    sort(e+1,e+nume+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=nume;i++){
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){
            k++;
            merge(u,v);
            tot+=e[i].dis;
            if(k>=n-1) break;
        }
    }
    //cout<<tot<<endl;
    if(k>=n-1){
        printf("%d ",tot);
    }else printf("orz");
    fclose(stdin);
    return 0;
}

prim,复杂度与dijkstra相似,稍后再看

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int MAXN=5005,MAXM=200005;
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
         if(c=='-') fh=-1;
         c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return rv*fh;
}
struct edge{
    int to,nxt,dis;
}e[MAXM*2];
int head[MAXN],dis[MAXN],n,m,tot,nume;
bool f[MAXN];
void adde(int from,int to,int dis){
    e[++nume].to=to;
    e[nume].dis=dis;
    e[nume].nxt=head[from];
    head[from]=nume;
}
int main(){
    freopen("in.txt","r",stdin);
    n=init();m=init();
    for(int i=1;i<=m;i++){
        int u=init(),v=init(),dii=init();
        adde(u,v,dii);adde(v,u,dii);
    }
    memset(dis,0x3f,sizeof(dis));
    f[1]=1;
    dis[1]=0;
    for(int i=head[1];i;i=e[i].nxt){
        dis[e[i].to]=min(dis[e[i].to],e[i].dis);
    }
    for(int i=2;i<=n;i++){
        int mi=0x3f3f3f3f,k=0;
        for(int i=1;i<=n;i++){
            if(!f[i]){
                if(dis[i]<mi){
                    mi=dis[i];k=i;
                }
            }
        }
        if(k==0){
            printf("orz");return 0;
        }
        tot+=mi;
        f[k]=1;
        //cout<<tot<<endl;
        for(int i=head[k];i;i=e[i].nxt){
            int v=e[i].to;
            dis[v]=min(dis[v],e[i].dis);
        }
    }
    printf("%d",tot);
    fclose(stdin);
    return 0;
}

图的连通性

tarjan

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <stack>
using namespace std;
const int MAXN=5005,MAXM=50005;
int read(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return rv*fh;
}
struct edge{
    int to,nxt;
}e[MAXM*2];
int head[MAXN],fa[MAXN],dfn[MAXN],low[MAXN],index,bcnt,nume,n,m,ma,k;
bool f[MAXN];
void adde(int from,int to){
    e[++nume].to=to;
    e[nume].nxt=head[from];
    head[from]=nume;
}
stack<int> st;
void tarjan(int u){
    dfn[u]=low[u]=++index;
    f[u]=1;
    st.push(u);
    int v=0;
    for(int i=head[u];i;i=e[i].nxt){
         v=e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(f[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        int tot=0;
        bcnt++;
        do{
            tot++;
            v=st.top();
            st.pop();
            f[v]=0;
            fa[v]=bcnt;
        }while(v!=u);
        if(tot>ma){
            ma=tot;
            k=bcnt;
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),t=read();
        adde(u,v);
        if(t==2) adde(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    printf("%d\n",ma);
    for(int i=1;i<=n;i++) 
        if(fa[i]==k) printf("%d ",i);
    fclose(stdin);
    return 0;
}

tarjan缩点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int MAXN=10005,MAXM=100005;
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
stack <int> sta;
struct edge{
    int to,from,nxt;
}e[MAXM],nww[MAXM];
int n,m,val[MAXN],inn[MAXN],nume,head[MAXN],dp[MAXN],fa[MAXN],ind,cnt,dfn[MAXN],low[MAXN],sum[MAXN],nwh[MAXN];
bool f[MAXN];
void adde(int from,int to){
    e[++nume].to=to;
    e[nume].nxt=head[from];
    head[from]=nume;
    e[nume].from=from;
}
void addn(int from,int to){
    nww[++nume].to=to;
    nww[nume].nxt=nwh[from];
    nwh[from]=nume;
}
void tarjan(int u){
    low[u]=dfn[u]=++ind;
    sta.push(u);
    f[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(f[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        cnt++;
        int v=0;
        do{
            v=sta.top();
            sta.pop();
            f[v]=0;
            fa[v]=cnt;
            sum[cnt]+=val[v];
        }while(v!=u);
    }
}
int main(){
    freopen("in.txt","r",stdin);
    n=init();m=init();
    for(int i=1;i<=n;i++){
        val[i]=init();
    }
    for(int i=1;i<=m;i++){
        int u=init(),v=init();
        adde(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    nume=0;
    for(int i=1;i<=m;i++){
        if(fa[e[i].from]!=fa[e[i].to]){
            addn(fa[e[i].from],fa[e[i].to]);
            inn[fa[e[i].to]]++;
        }
    }
    queue<int> q;
    for(int i=1;i<=cnt;i++){
        if(!inn[i]) {q.push(i);dp[i]=sum[i];}
        
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=nwh[u];i;i=nww[i].nxt){
            int v=nww[i].to;
            inn[v]--;
            dp[v]=max(dp[v],dp[u]+sum[v]);
            if(!inn[v]) q.push(v);
        }
    }//cout<<cnt;
    //for(int i=1;i<=n;i++) cout<<fa[i]<<endl;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    fclose(stdin);
    return 0;
}