loj121-动态图连通性-白红宇

loj121-动态图连通性

阅读量：6361 次

发布时间：2019-06-23

本文共 1625 字，大约阅读时间需要 5 分钟。

Solution

线段树分治, 然后直接在线段树上dfs, 在进入/回溯的过程中维护并查集的merge/split.

对于split操作, 可以在merge时按秩合并, 然后利用栈记录, split时恢复即可.

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            using namespace std;#define rep(i,l,r) for(register int i=(l);i<=(r);++i)#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)#define il inlinetypedef double db;typedef long long ll;//---------------------------------------const int nsz=5050,msz=5e5+50;int n,m;int edno[nsz][nsz],pe=0,pq=0,pq1=1;struct te{int f,t,l,r;}edge[msz];struct tq{int a,b,t,ans;}que[msz];int fa[nsz],dep[nsz];int stk[msz][2],top=0;//0 y; 1 dep[x]int find(int p){return p==fa[p]?p:find(fa[p]);}bool conn(int a,int b){return find(a)==find(b);}void merge(int a,int b){ a=find(a),b=find(b); if(a==b)return; if(dep[a]

ee[msz*4];#define ls(p) ((p)<<1)#define rs(p) ((p)<<1|1)void insert(int v,int l,int r,int rt,int rl,int rr){ if(l<=rl&&rr<=r){ee[rt].push_back(v);return;} int mid=(rl+rr)>>1; if(l<=mid)insert(v,l,r,ls(rt),rl,mid); if(mid

>1; dfs(ls(rt),rl,mid); dfs(rs(rt),mid+1,rr); } del(now);}int main(){// freopen("a.in","r",stdin);// freopen("a.out","w",stdout); ios::sync_with_stdio(0),cin.tie(0); cin>>n>>m; int a,b,c; rep(i,1,m){ cin>>a>>b>>c; if(b>c)swap(b,c); if(a==0){ edge[++pe]=(te){b,c,i,m}; edno[b][c]=pe; } else if(a==1){ edge[edno[b][c]].r=i; } else{ que[++pq]=(tq){b,c,i,0}; } } rep(i,1,n)fa[i]=i,dep[i]=1; rep(i,1,pe)insert(i,edge[i].l,edge[i].r,1,1,m); dfs(1,1,m); rep(i,1,pq){cout<<(que[i].ans?"Y":"N")<<'\n';} return 0;}

转载于:https://www.cnblogs.com/ubospica/p/10608486.html

你可能感兴趣的文章