bzoj4229(并查集)

Posted on   |   In

题目描述

现在，我想知道自己是否还有选择。

给定n个点m条边的无向图以及顺序发生的q个事件。

每个事件都属于下面两种之一：

1、删除某一条图上仍存在的边

2、询问是否存在两条边不相交的路径可以从点u出发到点v

题解

神奇的并查集 %%%%

我们考虑离线下来 从后到前做 把删边处理成加边(注意重边)

把剩下的边分成两部分 树边和非树边

然后对于询问上被删除的边 从后往前 分为树边和非树边

然后把两个部分树边构成生成树 并把初始情况下的非树边加入 对生成树缩点 用并查集维护

对于询问中还未加入的边 用并查集维护即可

对于询问的查询 只要判断两点在并查集中是否联通即可

时间复杂度$O(n+m)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,double>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e5+10;
const double eps=1e-4;
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
int n,m,q;
bool T[MAXN];
int f[MAXN],F[MAXN];
 
int find1(int x){
    if(x==f[x])return x;
    return f[x]=find1(f[x]);
}
 
int Find1(int x){
    if(x==F[x])return x;
    return F[x]=Find1(F[x]);
}
 
typedef struct node{
    int id,x,y;
    friend bool operator<(node aa,node bb){
        if(aa.x==bb.x)return aa.y<bb.y;
        return aa.x<bb.x;
    }
}node;
node d[MAXN],Edge[MAXN];
set<node>s;
set<node>::iterator ite; 
char str[11];
bool vis[MAXN],use[MAXN];
int dep[MAXN],fa[MAXN],sz[MAXN];
void dfs(int x,int pre,int deep){
    fa[x]=pre;dep[x]=deep+1;vis[x]=1;
    link(x){
        if(j->t==pre)continue;
        dfs(j->t,x,deep+1);
    }
}
stack<int>S;
int main(){
    n=read();m=read();q=read();
    inc(i,1,n)f[i]=i,F[i]=i,sz[i]=1;
    inc(i,1,m){
        Edge[i].x=read();Edge[i].y=read();
        if(Edge[i].x>Edge[i].y)swap(Edge[i].x,Edge[i].y);
        s.insert((node){i,Edge[i].x,Edge[i].y});
    }
    inc(i,1,q){
        scanf("%s %d %d",str,&d[i].x,&d[i].y);
        if(str[0]=='P')d[i].id=0;
        else{
            if(d[i].x>d[i].y)swap(d[i].x,d[i].y);
            d[i].id=1;
            ite=s.lower_bound((node){0,d[i].x,d[i].y});
            T[ite->id]=1;s.erase(ite);
        }
    }
    inc(i,1,m){
        if(T[i])continue;
        int t1=find1(Edge[i].x);int t2=find1(Edge[i].y);
        if(t1==t2)continue;
        f[t1]=t2;T[i]=1;
        add(Edge[i].x,Edge[i].y);
        add(Edge[i].y,Edge[i].x);
    }
    dec(i,q,1){
        if(!d[i].id)continue;
        int t1=find1(d[i].x);int t2=find1(d[i].y);
        if(t1==t2)continue;
        f[t1]=t2;use[i]=1;
        add(d[i].x,d[i].y);add(d[i].y,d[i].x);
    }
    inc(i,1,n)if(!vis[i])dfs(i,0,0);
    inc(i,1,m){
        if(T[i])continue;
        int x=Edge[i].x;int y=Edge[i].y;
        if(Find1(x)==Find1(y))continue;
        x=Find1(x);y=Find1(y);
        while(x!=y){
            if(dep[x]<dep[y])swap(x,y);
            F[x]=fa[x];x=Find1(x);
        }
    }
    dec(i,q,1){
        if(!d[i].id){
            if(Find1(d[i].x)==Find1(d[i].y))S.push(1);
            else S.push(0);
        }
        else{
            if(use[i])continue;
            int x=d[i].x;int y=d[i].y;
            if(Find1(x)==Find1(y))continue;
            x=Find1(x);y=Find1(y);
            while(x!=y){
                if(dep[x]<dep[y])swap(x,y);
                F[x]=fa[x];x=Find1(x);
            }               
        }
    }
    while(!S.empty()){
        if(S.top())puts("Yes");
        else puts("No");
        S.pop();
    }
    return 0;
}