一类图论问题

ini2015_____ · 2026-04-28 20:58:42 · 算法·理论

给你一个图，图的点数是 O(n) 的，但是边数可以是 O(n^2) 的，这个图的建边有一定规律，然后我们需要做图上的信息处理。

这些问题大部分都可以用优化建图的方法来解决，但是时空常数都较大。实际上存在一类通用性较强的方法来解决。

DFS/BFS/求生成树

以 P15180 为例题，发现一个事情，我们的朴素 BFS 是 O(n+m) 的，其中 O(m) 的部分其实是对一个点枚举它所有的出边，虽然可能有 O(n^2) 个出边，但是这里面真正有用的只有 O(n) 个，其他的出边连到的都是已经访问过的点。

也就是说，当我们 BFS 到 u 时，我们实际上只需要知道与 u 相连的点中哪些点没有被访问。

假设 i 向 [0,x_i]\times [0,y_i] 范围内的点连边，那么我们查询 [0,x_i] 范围内 y 最小的没有被访问的点，如果最小的 y 也 >y_i，那就倒闭了，否则我们把 y 最小的那个点加到队列里面。P15180 也能转成类似的偏序关系，线段树维护即可 O(n\log n)。 ::::info[code 1]

const int N=2e5+5,inf=1e9+7;
int n,s,t,T;
int a[N];
bool del[N];
int dis[N];
int vf[N],vg[N],vh[N];
struct Node{int mx,p;};
Node operator+(Node a,Node b){
    Node c; c.mx=max(a.mx,b.mx);
    if(a.mx==c.mx)c.p=a.p;
    if(b.mx==c.mx)c.p=b.p;
    return c;
}
struct SegmentTree{
    Node tr[N<<2];    
    #define mid ((l+r)>>1)
    #define lson u<<1,l,mid
    #define rson u<<1|1,mid+1,r
    #define root 1,1,n
    void pushup(int u){
        tr[u]=tr[u<<1]+tr[u<<1|1];
    }
    void build(int u,int l,int r,int* v){
        if(l==r){
            tr[u].p=l,tr[u].mx=v[l];
            return ;
        }
        build(lson,v),build(rson,v);
        pushup(u);
    }
    void erase(int u,int l,int r,int p){
        if(l==r){return (void)(tr[u].mx=-inf);}
        if(p<=mid)erase(lson,p);
        if(p> mid)erase(rson,p);
        pushup(u);
    }
    Node query(int u,int l,int r,int x,int y){
        if(x<=l&&r<=y)return tr[u];
        if(x> mid)return query(rson,x,y);
        if(y<=mid)return query(lson,x,y);
        return query(lson,x,y)+query(rson,x,y);
    }
}F,G,H;
void erase(int x){
    del[x]=1; 
    F.erase(root,x),G.erase(root,x),H.erase(root,x);
}
void solve(){
    n=read(),s=read(),t=read();
    for(int i=1;i<=n;i++)a[i]=read(),del[i]=0;
    for(int i=1;i<=n;i++)vf[i]=a[i];
    for(int i=1;i<=n;i++)vg[i]=a[i]+i;
    for(int i=1;i<=n;i++)vh[i]=a[i]-i;
    F.build(root,vf),G.build(root,vg),H.build(root,vh);
    queue<int> q;
    q.push(s); dis[s]=0; erase(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        while(1){
            auto x=F.query(root,u-a[u],u+a[u]);
            if(x.mx<vf[u])break;
            else dis[x.p]=dis[u]+1,erase(x.p),q.push(x.p);
        }
        while(1){
            auto x=G.query(root,u-a[u],u);
            if(x.mx<u)break;
            else dis[x.p]=dis[u]+1,erase(x.p),q.push(x.p);
        }
        while(1){
            auto x=H.query(root,u,u+a[u]);
            if(x.mx<-u)break;
            else dis[x.p]=dis[u]+1,erase(x.p),q.push(x.p);
        }
    }
    printf("%d\n",dis[t]);
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}
//  Think twice,code once

::::

变种 1

假设给一个稠密图，使用 bitset 存图，要求 O(\frac{n^2}w) 做 BFS。

同样的道理，我们 BFS 的时候找到一个没有被访问的点，维护一个 bitset vis 表示当前还没有被访问的集合，每次把 vis 和 u 邻域的 bitset 取 and，每次用 _Find_next 找到下一个 0 即可。 ::::info[code 2] Source：ini P11369 的代码。

Bit all;
bool bfs(int s,int t){
    queue<int> q; q.push(s);
    for(int i=1;i<=idx;i++)all[i]=1;
    all[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        if(u==t)return true;
        Bit Q=all&e3[u];
        int v=Q._Find_next(0);
        while(v<=idx){
            q.push(v),all[v]=0;
            v=Q._Find_next(v);
        }
    }
    return false;
}

::::

变种 2

给一个图的补图，做 BFS，要求 O(n+m)。

非常简单，维护一个 set 表示其当前还未被访问的集合，一个点被访问的时候把他从 set 中删除，每次暴力遍历邻域，遇到能走的点就把他加到队列里面。不能走的点就不管他，这样的事情只会发生 m 次。

发现 set 还是菜了，换成链表即可，时间复杂度 O(n+m)。

求拓扑序

拓扑排序也是可以用 DFS 来实现的！

每次我们希望删掉一个点 u，在删掉 u 前需要把所有连向 u 的点全部删掉，那么我们依旧需要做一个找到邻域所有未被删除的点的过程，以 P12031 为例，这里直接线段树找到 x 在一个前缀内 y 最小的删掉即可。

::::info[code 3]

const int N=1e5+5,inf=1e9+7;
int n,m,T,Testid;
bool del[N];
int x_1[N],y_1[N],x_2[N],y_2[N];
int fy[N<<1],dt[N<<1];
struct SegmentTree{
    pii tr[N<<3];
    #define mid ((l+r)>>1)
    #define lson u<<1,l,mid
    #define rson u<<1|1,mid+1,r
    #define root 1,1,2*n
    void pushup(int u){
        tr[u]=min(tr[u<<1],tr[u<<1|1]);
    }
    void build(int u,int l,int r){
        if(l==r){
            tr[u]=mkp(fy[l],dt[l]);
            return ;
        }
        build(lson),build(rson);
        pushup(u);
    } 
    void del(int u,int l,int r,int p){
        if(l==r)return (void)(tr[u].fi=inf);
        if(p<=mid)del(lson,p);
        if(p> mid)del(rson,p);
        pushup(u);
    }
    void add(int u,int l,int r,int p){
        if(l==r)return (void)(tr[u].fi=fy[l]);
        if(p<=mid)add(lson,p);
        if(p> mid)add(rson,p);
        pushup(u);
    }
    pii query(int u,int l,int r,int x,int y){
        if(x<=l&&r<=y)return tr[u];
        if(x> mid)return query(rson,x,y);
        if(y<=mid)return query(lson,x,y);
        return min(query(lson,x,y),query(rson,x,y));
    }
}F;
void build(){
    for(int i=1;i<=2*n;i++)fy[i]=inf;
    for(int i=1;i<=n;i++)fy[x_1[i]]=y_1[i],dt[x_1[i]]=i;
    F.build(root);
}
int seq[N],idx;
void erase(int u){seq[++idx]=u,del[u]=1; F.del(root,x_1[u]);}
void topo(int u){
    while(1){
        F.del(root,x_1[u]);
        auto v=F.query(root,1,x_2[u]);
        F.add(root,x_1[u]);
        if(v.fi< y_2[u])topo(v.se);
        else return erase(u);
    }
}
void solve1(){
    n=read();
    for(int i=1;i<=n;i++)x_1[i]=read(),y_1[i]=read(),x_2[i]=read(),y_2[i]=read(),del[i]=0;
    build(); idx=0;
    for(int i=1;i<=n;i++)if(!del[i])topo(i);
    for(int i=1;i<=idx;i++)printf("%d ",seq[i]);
    printf("\n");
}

::::

求强连通分量

tarjan 的过程同样不能用优化建边之类的维护，但是我们可以使用 kosaraju，kosaraju 是一个只使用 DFS 来求 scc 的算法，正好我们会 DFS！正反两遍 DFS，即可求出强连通分量。

P6898 直接使用这个技巧，即可 O(\frac{n^4}{w}) 草过去。

P9139 中使用这个技巧，就能空间 O(n) 做了。 ::::info[code 4]

const int N=2e5+5,inf=1e9+7;
int n,m,T;
int ps[N][4],ct[N];
struct Vertex{
    int l1,r1;
    int l2,r2;
}a[N<<1];
bool ans[N];
struct SegmentTree{
    pii tr1[N<<2],tr2[N<<2];
    set<pii> f[N];
    #define mid ((l+r)>>1)
    #define lson u<<1,l,mid
    #define rson u<<1|1,mid+1,r
    #define root 1,1,4*n
    void pushup(int u){
        tr1[u]=max(tr1[u<<1],tr1[u<<1|1]);
        tr2[u]=min(tr2[u<<1],tr2[u<<1|1]);
    }
    void init(int u,int l){
        if(f[l].empty()){tr1[u].fi=-inf,tr2[u].fi=inf; return ;}
        tr1[u]=*f[l].rbegin();
        tr2[u]=*f[l].begin();
    }
    void build(int u,int l,int r){
        if(l==r)return f[l].clear(),init(u,l);
        build(lson),build(rson);
        pushup(u);
    }
    void del(int u,int l,int r,int p,int y,int v){
        if(l==r){
            f[l].erase(mkp(y,v));
            return init(u,l);
        }
        if(p<=mid)del(lson,p,y,v);
        if(p> mid)del(rson,p,y,v);
        pushup(u);
    }
    void add(int u,int l,int r,int p,int y,int v){        
        if(l==r){
            f[l].insert(mkp(y,v));
            return init(u,l);
        }
        if(p<=mid)add(lson,p,y,v);
        if(p> mid)add(rson,p,y,v);
        pushup(u);
    }
    pii query1(int u,int l,int r,int x,int y){
        if(y< x)return mkp(-inf,0);
        if(x<=l&&r<=y)return tr1[u];
        if(x> mid)return query1(rson,x,y);
        if(y<=mid)return query1(lson,x,y);
        return max(query1(lson,x,y),query1(rson,x,y));
    }
    pii query2(int u,int l,int r,int x,int y){
        if(y< x)return mkp(inf,0);
        if(x<=l&&r<=y)return tr2[u];
        if(x> mid)return query2(rson,x,y);
        if(y<=mid)return query2(lson,x,y);
        return min(query2(lson,x,y),query2(rson,x,y));
    }
}F;
vector<int> s;
bool vis[N]; int bid[N],scc;
void init(){
    F.build(root);
    for(int i=1;i<=2*n;i++){
        F.add(root,a[i].l1,a[i].r1,i);
        F.add(root,a[i].l2,a[i].r2,i);
    }
}
void erase(int u){
    F.del(root,a[u].l1,a[u].r1,u);
    F.del(root,a[u].l2,a[u].r2,u);
}
int pa(int u){return (u<=n)?(u+n):(u-n);}
void dfs1(int u){
    erase(pa(u)); vis[u]=1;
    while(1){
        auto t=F.query1(root,1,a[u].l1-1);
        if(t.fi<=a[u].r1)break;
        dfs1(pa(t.se));
    }
    while(1){
        auto t=F.query2(root,a[u].l1,4*n);
        if(t.fi>=a[u].r1)break;
        dfs1(pa(t.se));
    }
    while(1){
        auto t=F.query1(root,1,a[u].l2-1);
        if(t.fi<=a[u].r2)break;
        dfs1(pa(t.se));
    }
    while(1){
        auto t=F.query2(root,a[u].l2,4*n);
        if(t.fi>=a[u].r2)break;
        dfs1(pa(t.se));
    }
    s.pb(u);
}
void dfs2(int u){
    bid[u]=scc; erase(u);
    u=pa(u);
    while(1){
        auto t=F.query1(root,1,a[u].l1-1);
        if(t.fi<=a[u].r1)break;
        dfs2(t.se);
    }
    while(1){
        auto t=F.query2(root,a[u].l1,4*n);
        if(t.fi>=a[u].r1)break;
        dfs2(t.se);
    }
    while(1){
        auto t=F.query1(root,1,a[u].l2-1);
        if(t.fi<=a[u].r2)break;
        dfs2(t.se);
    }
    while(1){
        auto t=F.query2(root,a[u].l2,4*n);
        if(t.fi>=a[u].r2)break;
        dfs2(t.se);
    }
}
void kosaraju(){
    init();
    for(int i=1;i<=2*n;i++)if(!vis[i])dfs1(i);
    init();
    reverse(s.begin(),s.end());
    for(int v:s)if(!bid[v])++scc,dfs2(v);
}
void report(int o){
    if(!o){printf("No\n"); exit(0);}
    printf("Yes\n");
    for(int i=1;i<=4*n;i++)printf("%d",ans[i]);
}
int main(){
    n=read();
    for(int i=1,x;i<=4*n;i++)
        x=read(),ps[x][ct[x]++]=i;
    for(int i=1;i<=n;i++){
        a[i].l1=ps[i][0],a[i].r1=ps[i][1],
        a[i].l2=ps[i][2],a[i].r2=ps[i][3];
        a[i+n].l1=ps[i][0],a[i+n].r1=ps[i][2],
        a[i+n].l2=ps[i][1],a[i+n].r2=ps[i][3];
    }
    kosaraju();
    for(int i=1;i<=n;i++){
        if(bid[i]==bid[i+n])report(0);
        else if(bid[i]<bid[i+n])ans[a[i+n].l1]=ans[a[i+n].l2]=1;
        else ans[a[i].l1]=ans[a[i].l2]=1;
    }
    report(1);
    return 0;
}
//  Think twice,code once

::::

求边双连通分量/点双连通分量

zfr 教我了一个求边双的做法，我称之为 zfr 算法。

考虑 DFS 一遍求出每个点的 dfn 序，然后假如 a\to b 有连边且 dfn_a<dfn_b，那么在新图中连有向边 a\to b，在新图中 kosaraju 即可。可以证明新图中的 scc 对应原图中的点双。

不难发现，原来二维限制的连边变成了三维限制，只能 O(n\log^2 n)，原来 bitset 的限制还是 bitset，依旧 O(\frac{n^2}{w})。

知名选手 Purslane 教了我一个更牛的做法。

考虑 tarjan 的过程，我们实际上需要只要一个位置的 low 值，也就是子树内部能够走到的 dfn 最小值。

先 DFS 一遍求出每个点的 dfn，拉出来一颗生成树，记 u 树上的邻域是 T_u，原图上的邻域是 G_u，那我们要求 G_u\setminus T_u 内部 dfn 的最小值，记这个值为 pur，这也就是这个点对 low 的贡献。

把所有点按照 dfn 排序，从小到大把点给拉出来，看哪些点连向了这个点，这些点的 pur 值就已经确定了，就可以把这些点删掉了。

假设求边双的话，G_u 内部 dfn 最小值和 G_u\setminus T_u 内部 dfn 最小值没区别，求点双的话，要把 fa_u 给去掉，这和刚才的变种 2 是差不多的。

这样子求边双和点双，对于偏序关系的连边可以 O(n\log n)，bitset 连边可以 O(\frac{n^2}{w})。

不知道有什么题目使用了这个东西，我也没有写代码。