南外Day5-图的连通性

Posted on By 陈麒润 南外Day5-图的连通性无评论

今天就不放题目代码了，放模板

low数组立大功

缩点

#include<bits/stdc++.h>
#define MX 100001
using namespace std;
int n,m,x,z,sc,ts,sm,me,su,flag,rd[MX];
int low[MX],dfn[MX],f[MX],col[MX];
int nt[MX],cd[MX],st2[MX],qz[MX];
bool che[MX];
vector<int> vx[MX],vt[MX];
queue<int> q;stack<int> s;
void tarj(int u){
    ts++;che[u]=1;
    dfn[u]=low[u]=ts;
    s.push(u);
    for(auto v:vt[u]){
        if(!dfn[v]){
            tarj(v);
            low[u]=min(low[u],low[v]);
        }else if(che[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        int t;
        do{
            t=s.top();che[t]=0;
            s.pop();col[t]=u;
            if(t==u){break;}
            qz[u]+=qz[t];
        }while(!s.empty());
        st2[sc]=0;
    }
    return;
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){cin>>qz[i];}
    for(int i=1;i<=m;i++){
        cin>>x>>z;
        vt[x].push_back(z);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarj(i);
    for(int i=1;i<=n;i++){x=i;
        for(auto y:vt[x]){
            if(col[x]!=col[y]){
                vx[col[x]].push_back(col[y]);
                rd[col[y]]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(!rd[i]){q.push(i);f[i]=qz[i];}
    while(!q.empty()){
        x=q.front();q.pop();
        for(auto y:vx[x]){
            f[y]=max(f[y],f[x]+qz[y]);
            if(!--rd[y]){q.push(y);}
        }
    }
    x=0;
    for(int i=1;i<=n;i++){x=max(x,f[i]);}
    cout<<x;
    return 0;
}

割点

x->y且low[y]>=dfn[x]

#include<bits/stdc++.h>
#define MX 100001
using namespace std;
int n,m,x,z,ts,flag,cnt,ans[MX];
int low[MX],dfn[MX],col[MX];
int nt[MX],cd[MX],st2[MX];
bool che[MX];
vector<int> vx[MX],vt[MX];
queue<int> q;stack<int> s;
void tarj(int u,int rt){
    ts++;dfn[u]=low[u]=ts;
    s.push(u);int cke=(u!=rt);
    for(auto v:vt[u]){
        if(!dfn[v]){
            tarj(v,rt);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])//走不回u前面 
                cke++;
        }else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(cke>=2){ans[++cnt]=u;}
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>z;
        vt[x].push_back(z);
        vt[z].push_back(x);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarj(i,i);
    cout<<cnt<<&#039;\n&#039;;
    sort(ans+1,ans+1+cnt);
    for(int i=1;i<=cnt;i++)
        cout<<ans[i]<<&#039; &#039;;
    return 0;
}

边双连通分量

x->y且low[y]>dfn[x]，为割边（需要点特判）

搜索除了割边以外的节点

#include<bits/stdc++.h>
#define MX 4000001
#define MP make_pair
#define GP pair<int,int>
using namespace std;
int n,m,x,z,ts,flag,cnt,ans;
int low[MX],dfn[MX],col[MX];
int nt[MX],cd[MX],st2[MX];
bool che[MX],ceg[MX];
vector<int> va[MX];
vector<GP> vt[MX];
queue<int> q;stack<int> s;
void tarj(int u,int rt){
    ts++;s.push(u);
    dfn[u]=low[u]=ts;
    for(auto edge:vt[u]){
        int v=edge.first,id=edge.second;
        if(!dfn[v]){
            tarj(v,id);
            if(dfn[u]<low[v]){ceg[id]=ceg[id^1]=1;}
            low[u]=min(low[u],low[v]);
        }else if(id!=(rt^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void dfs(int u,int nw){
    col[u]=nw;va[nw].push_back(u);
    for(auto edge:vt[u]){
        int v=edge.first,id=edge.second;
        if(ceg[id] || col[v]) continue;
        dfs(v,nw);
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>z;
        vt[x].push_back(MP(z,i*2));
        vt[z].push_back(MP(x,i*2+1));
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarj(i,0);
    for(int i=1;i<=n;i++)
    if(!col[i]) dfs(i,++ans);
    cout<<ans<<&#039;\n&#039;;
    for(int i=1;i<=ans;i++){
        cout<<va[i].size()<<&#039; &#039;;
        for(auto v:va[i]){cout<<v<<&#039; &#039;;}
        cout<<&#039;\n&#039;;
    }
    return 0;
}

点双连通分量

和割点差不多，注意割点不能弹栈

#include<bits/stdc++.h>
#define MX 4000001
#define MP make_pair
#define GP pair<int,int>
using namespace std;
int n,m,x,z,ts,flag,cnt,ans,bgc;
int low[MX],dfn[MX],col[MX];
int nt[MX],cd[MX],st2[MX],brg[MX][2];
bool che[MX],ceg[MX];
vector<int> va[MX],vt[MX];
queue<int> q;stack<int> s;
void tarj(int u,int rt){
    ts++;s.push(u);
    dfn[u]=low[u]=ts;
    if(u==rt && !vt[u].size()){
        va[++ans].push_back(u);
        return;
    }
    for(auto v:vt[u]){
        if(!dfn[v]){
            tarj(v,rt);
            if(low[v]>=dfn[u]){
                ans++;int t;
                do{
                    t=s.top();s.pop();
                    va[ans].push_back(t);
                    if(t==v) break;
                }while(!s.empty());
                va[ans].push_back(u);
            }
            low[u]=min(low[u],low[v]);
        }else{low[u]=min(low[u],dfn[v]);}
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>z;if(x==z) continue;
        vt[x].push_back(z);
        vt[z].push_back(x);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarj(i,i);
    cout<<ans<<&#039;\n&#039;;
    for(int i=1;i<=ans;i++){
        cout<<va[i].size()<<&#039; &#039;;
        for(auto v:va[i]){cout<<v<<&#039; &#039;;}
        cout<<&#039;\n&#039;;
    }
    return 0;
}

圆方树

把所有的点双/边双（看实际情况）用一个方点连为一个菊花图，然后就构成了一个圆点和方点相邻的树

例题 P4320

#include<bits/stdc++.h>
#define MX 1000001
#define MP make_pair
#define GP pair<int,int>
using namespace std;
int n,m,x,z,ts,flag,cnt,ans,bgc,Jmp=25;
int low[MX],dfn[MX],col[MX],dep[MX],f[MX][30];
int nt[MX],gd[MX],st2[MX],brg[MX][2];
bool che[MX],ceg[MX];
vector<int> va[MX],vt[MX];
queue<int> q;stack<int> s;
void dfs(int u);void cst();int LCA(int x,int y);
void tarj(int u,int rt){
    ts++;dfn[u]=low[u]=ts;
    s.push(u);
    for(auto v:vt[u]){
        if(!dfn[v]){
            tarj(v,rt);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ans++;int t;
                do{
                    t=s.top();s.pop();
                    va[t].push_back(ans);
                    va[ans].push_back(t);
                    //cout<<t<<&#039; &#039;<<ans<<&#039;\n&#039;;
                    if(t==v) break;
                }while(!s.empty());
                //cout<<u<<&#039; &#039;<<ans<<&#039;\n&#039;;
                va[u].push_back(ans);
                va[ans].push_back(u);
            }
        }else{low[u]=min(low[u],dfn[v]);}
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>m;ans=n;
    for(int i=1;i<=m;i++){
        cin>>x>>z;if(x==z) continue;
        brg[i][0]=x;brg[i][1]=z;
        vt[x].push_back(z);
        vt[z].push_back(x);
    }
    //cout<<&#039;\n&#039;;
    for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarj(i,i);
    n=ans;
    dfs(1);cst();
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>z;
        if(!x){return 0;}
        int lca=LCA(x,z);//cout<<lca<<&#039;-&#039;;
        cout<<(dep[x]+dep[z]-dep[lca]*2)/2+1<<&#039;\n&#039;;
    }
    return 0;
}
void dfs(int u){
    for(auto v:va[u]){
        if(f[u][0]==v){continue;}
        dep[v]=dep[u]+1;
        f[v][0]=u;dfs(v);
    }
}
void cst(){
    for(int i=1;i<=Jmp;i++)
    for(int j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y){
    if(dep[x]>dep[y]){swap(x,y);}
    for(int i=Jmp;i+1;i--)
    if(dep[f[y][i]]>=dep[x])
        y=f[y][i];
    if(x==y){return x;}
    for(int i=Jmp;i+1;i--)
    if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
训练日志

发表回复