题解：P10350 [PA2024] Modernizacja Bajtocji

· · 题解

很精妙的一道智商题，没想出来。。。

一个显然的想法：考虑 a_i,b_i 连边。然后就不会了。

观察一个大小为 n 的连通块有没有什么高妙的性质。可以发现，这个连通块最少有 n-1 条边，但最多也只有 n 条边。因为每次连边意味着电脑送给了一个未曾有过电脑的人，而整个连通块里最多就 n 个人有电脑，所以最多也只能送 n 次，就是 n 条边。

进一步容易发现，一个边数为 n 的连通块（注意不一定是简单环，因为可能有自环）里的所有人一定都有电脑，而边数为 n-1 的连通块（也就是一棵树）里恰好有一个人没有电脑，但是我们确定不了那个人是谁。

接下来考虑删点。

可以发现，这个操作包含两个部分，第一个是这个点曾经有电脑的信息，第二个是纯粹要从图里删掉这个点，把这个点单点变成一个新的连通块。

对于第二个部分，为了不影响其他点上已有的信息，我们把这个操作看成把这个点从它所在的连通块里复制一个新点出来，以后在用这个点的时候都用新点。

考虑这个点曾经有电脑的信息有没有什么用。对于 n 条边的情况，显然没有用；对于 n-1 条边的情况，显然如果只有两个点那么另一个点肯定没有电脑，但这个信息对于之后的操作没有用，而对于更多点的情况，由于我们不知道这个点是什么时候有了电脑，所以根本没办法推理任何信息，也就是说，其他点还是未知状态，这条信息没有用。

总而言之，这个信息只能在树状连通块且 n=2 时产生影响，表示另一个点一定没有电脑。

那么查询的时候判断所在连通块中的边数为 n 或 n-1，再特判 n=2 树状连通块和 n=1 即可。

使用并查集可以轻易维护以上所有内容。自环可以正常维护。需要注意删点会改变 n 的大小。

代码经过精巧实现并不难写：

int n,q;
int fa[N*5],eg[N*5],siz[N*5];
int re[N];
int tot;
bool info[N];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int opp[N];
int main(){
#ifdef ly
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>q;
    tot=n;
    fr1(i,1,n) fa[i]=re[i]=i,eg[i]=0,siz[i]=1;
    while(q--){
        char op;
        int x,y;
        cin>>op;
        if(op=='-'){
            cin>>x;
            siz[find(re[x])]--;
            eg[find(re[x])]--;
            tot++;
            re[x]=fa[tot]=tot;
            siz[tot]=1,eg[tot]=0;
        }
        else if(op=='+'){
            cin>>x>>y;
            int rx=re[x],ry=re[y];
            if(find(rx)==find(ry)) eg[find(rx)]++;
            else eg[find(rx)]+=eg[find(ry)]+1,siz[find(rx)]+=siz[find(ry)],fa[find(ry)]=find(rx);
        }
        else if(op=='?'){
            cin>>x;
            if(siz[find(re[x])]==1&&eg[find(re[x])]!=1) cout<<"0";
            else{
                if(siz[find(re[x])]==eg[find(re[x])]) cout<<"1";
                else cout<<"?";
            }
        }
    }
    ET;
}